回溯问题
三种情况
每种情况都有子集，组合，排列三种题型
无重复元素不可复选
//子集问题
static List<list<integer>> res=new LinkedList<>();
   static LinkedList<integer> track=new LinkedList<>();
   //无重复元素
   public static List<list<integer>> subsets(int[] nums) {
       back(nums,0);
       return res;
  }
​
   static void back(int[] nums,int start){
       res.add(new LinkedList<>(track));
       for (int i=start;i<nums.length;i++){ track.add(nums[i]); back(nums,i+1); track.removelast(); } 组合问题 static list<list<integer>> res=new LinkedList<>();
   static LinkedList<integer> track=new LinkedList<>();
   public static List<list<integer>> combine(int n, int k) {
       backtrack(n,1,k);
       return res;
  }
   static void backtrack(int n,int start,int k){
       if(track.size()==k){
           res.add(new LinkedList<>(track));
      }
       for (int i=start;i<=n;i++){ track.add(i); backtrack(n,i+1,k); track.removelast(); } 排列问题 static list<list<integer>> res=new LinkedList<>();
   static LinkedList<integer> track=new LinkedList<>();
   public static List<list<integer>> permute(int[] nums) {
     back(nums,track);
     return res;
  }
​
   static void back(int[] nums,LinkedList<integer> track){
       if(track.size()== nums.length){
           res.add(new LinkedList<>(track));
           return;
      }
       for (int i=0;i<nums.length;i++){ if(track.contains(nums[i])) continue; track.add(nums[i]); back(nums,track); track.removelast(); } }< code></nums.length;i++){></integer></list<integer></integer></=n;i++){></list<integer></integer></nums.length;i++){></list<integer></integer></list<integer>
有重复元素不可复选
//子集问题
List<list<integer>> res = new LinkedList<>();
LinkedList<integer> track = new LinkedList<>();
​
public List<list<integer>> subsetsWithDup(int[] nums) {
   // 先排序，让相同的元素靠在一起
   Arrays.sort(nums);
   backtrack(nums, 0);
   return res;
}
​
void backtrack(int[] nums, int start) {
   // 前序位置，每个节点的值都是一个子集
   res.add(new LinkedList<>(track));
 
   for (int i = start; i < nums.length; i++) {
       // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
       if (i > start && nums[i] == nums[i - 1]) {
           continue;
      }
       track.addLast(nums[i]);
       backtrack(nums, i + 1);
       track.removeLast();
  }
}
//组合问题
List<list<integer>> res = new LinkedList<>();
​
LinkedList<integer> track = new LinkedList<>();
​
int trackSum = 0;
​
public List<list<integer>> combinationSum2(int[] candidates, int target) {
   if (candidates.length == 0) {
       return res;
  }
   // 先排序，让相同的元素靠在一起
   Arrays.sort(candidates);
   backtrack(candidates, 0, target);
   return res;
}
​
void backtrack(int[] nums, int start, int target) {
       if (trackSum == target) {
       res.add(new LinkedList<>(track));
       return;
  }
 
   if (trackSum > target) {
       return;
  }
​
 
   for (int i = start; i < nums.length; i++) {
       // 剪枝逻辑，值相同的树枝，只遍历第一条
       if (i > start && nums[i] == nums[i - 1]) {
           continue;
      }
 
       track.add(nums[i]);
       trackSum += nums[i];
 
       backtrack(nums, i + 1, target);
 
       track.removeLast();
       trackSum -= nums[i];
  }
}
//排列问题
List<list<integer>> res = new LinkedList<>();LinkedList<integer> track = new LinkedList<>();
boolean[] used;
​
public List<list<integer>> permuteUnique(int[] nums) {
   // 先排序，让相同的元素靠在一起
   Arrays.sort(nums);
   used = new boolean[nums.length];
   backtrack(nums);
   return res;
}
​
void backtrack(int[] nums) {
   if (track.size() == nums.length) {
       res.add(new LinkedList(track));
       return;
  }
​
   for (int i = 0; i < nums.length; i++) {
       if (used[i]) {
           continue;
      }
       // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
       if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
           continue;
      }
       track.add(nums[i]);
       used[i] = true;
       backtrack(nums);
       track.removeLast();
       used[i] = false;
  }
}</list<integer></integer></list<integer></list<integer></integer></list<integer></list<integer></integer></list<integer>
无重复元素可复选
​
​
//子集问题
List<list<integer>> res = new LinkedList<>();
​
LinkedList<integer> track = new LinkedList<>();
​
int trackSum = 0;
​
public List<list<integer>> combinationSum(int[] candidates, int target) {
   if (candidates.length == 0) {
       return res;
  }
   backtrack(candidates, 0, target);
   return res;
}
​
​
void backtrack(int[] nums, int start, int target) {
 
   if (trackSum == target) {
       res.add(new LinkedList<>(track));
       return;
  }
 
   if (trackSum > target) {
       return;
  }
​
 
   for (int i = start; i < nums.length; i++) {
 
       trackSum += nums[i];
       track.add(nums[i]);
 
 
       backtrack(nums, i, target);
 
       trackSum -= nums[i];
       track.removeLast();
  }
}
​
//排列问题
List<list<integer>> res = new LinkedList<>();
LinkedList<integer> track = new LinkedList<>();
​
public List<list<integer>> permuteRepeat(int[] nums) {
   backtrack(nums);
   return res;
}
​
​
void backtrack(int[] nums) {
 
   if (track.size() == nums.length) {
 
       res.add(new LinkedList(track));
       return;
  }
​
 
   for (int i = 0; i < nums.length; i++) {
 
       track.add(nums[i]);
   
       backtrack(nums);
     
       track.removeLast();
  }</list<integer></integer></list<integer></list<integer></integer></list<integer>
Original: https://www.cnblogs.com/zz01/p/16616245.html
Author: 山野村夫01
Title: 回溯问题学习总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/622138/
转载文章受原作者版权保护。转载请注明原作者出处！