leetcode-回溯算法

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

这个题目在全排列Ⅰ的基础上多了去重这一步。

class Solution { boolean [] visited; public List> permuteUnique(int[] nums) { visited=new boolean[nums.length]; Arrays.sort(nums); List> res=new ArrayList<>(); List path =new ArrayList<>(); backtrack(nums,0,res,path);return res; } public void backtrack(int []nums,int idx,List> res,List path ){ if(idx==nums.length){ res.add(new ArrayList<>(path)); } for(int i=0;i0&&nums[i]==nums[i-1]&&!visited[i-1]){ continue; } path.add(nums[i]){ visited[i]==true; backtrack(nums,idx+1,res,path); visited[i]=false; path.remove(path.size()-1); } } } }

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

class Solution { private List> res = new ArrayList<>(); public List> combinationSum2(int[] candidates, int target) { List path =new ArrayList<>(); Arrays.sort(candidates); bactrack(path,candidates,target,0); return res; } private void backtrack(List path,int[] candidates,int target,int idx) { if(target==0){ res.add(new ArrayList<>(path)); } for(int i=idx;iidx&&candidates[i]==candidates[i-1]) continue; int num=target-candidates[i]; if(num>=0){ path.add(candidates[i]); backtrack(path,candidates,num,idx+1); path.remove(path.size()-1); } else{ return; } } }}