leetcode-回溯算法(去重)
- 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
这个题目在全排列Ⅰ的基础上多了去重这一步。
class Solution {
boolean [] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
visited=new boolean[nums.length];
Arrays.sort(nums);
List<List<Integer>> res=new ArrayList<>();
List<Integer> path =new ArrayList<>();
backtrack(nums,0,res,path);
return res;
}
public void backtrack(int []nums,int idx,List<List<Integer>> res,List<Integer> path ){
if(idx==nums.length){
res.add(new ArrayList<>(path));
}
for(int i=0;i<nums.length;i++){
if(visited[i]||i>0&&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);
}
}
}
}
- 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> path =new ArrayList<>();
Arrays.sort(candidates);
bactrack(path,candidates,target,0);
return res;
}
private void backtrack(List<Integer> path,int[] candidates,int target,int idx) {
if(target==0){
res.add(new ArrayList<>(path));
}
for(int i=idx;i<candidates.length;i++){
if(i>idx&&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;
}
}
}
}
