一般来说排列组合类的题目都是可以用回溯来求出所以的可能组合，回溯的本质就是用for暴力搜索，选取过程可以看做是一个树，分为同一树层选取和同一树枝选取。最近刷了几道题目，总结一下自己的理解：
一、回溯参数的设置
回溯的参数的设置一般是看回溯递归的过程中需要传入哪些变量就设置什么参数。下面是常见的几个参数设置：
①在组合中，一般是每个元素只能选一次（有些题目是可以重复选自己，题目会清楚说某一个元素可以无限次重复选取，如下面这个组合总和题目，这种情况下一层选取时是可以重复选自己的），
https://leetcode.cn/problems/combination-sum/
所以需要在下一层选取时改变起始条件，这个时候递归的参数就要有一个整型的startIndex来调整每一层的下标。
②如果有组合选取的条件，如总和需要满足什么条件，子串满足回文符等之类的，那么就需要传入这些参数。
二、回溯的去重问题：
回溯的去重分为同一树层去重、同一树枝去重，这两种情况的代码细节区别还是很大的：
①组合一般不用考虑同一树枝去重，只要考虑同一树层之间的去重；
②排列一般都需要考虑同一树枝即不同层之间的去重问题，如果待选取数组中有重复元素出现，那么还需要考虑同一树枝的去重，具体要看题目条件。
③根据去重方法，我又将同一树枝间的去重分为只重复1次元素的去重和重复2次以上的元素的去重。在有重复元素的数组的排列中，肯定有元素会出现2次以上，例如[1,1,2]的全排列，1这个元素就会在选择第一个1之后的下一层选取中重复出现两次。而例如[1,2,3]，每一个元素在下一层就只会出现1次。
④对于待选取数组中有重复元素，不管是组合还是排列问题，有两种去重思路：1、能先排序就先排序（Arrays.sort()）②不能排序的
三，去重的方法：
①对于组合的去重，因为一般只用考虑同一层去重，而在组合问题中，之所以会出现同一层的重复就是因为待选数组中有重复元素，只有这样组合中才要去重，这种情况如上面的第④点所说，有两种方法可以：
a、先对待选取数组进行排序操作，然后再建立一个标记数组markedArr[nums.length]，长度为待选区数组的长度，标记数组markedArr[i]和nums[i]一 一对应，同一层之间标记成功（markedArr[i] = 1）后进行标记回溯。
原理：当进入递归即进入下一层的选取时，如果出现重复元素，则markedArr[i - 1]在上一层还没被回溯，这个时候markedArr[i] = 0；但是在同一层可就会被回溯掉，markedArr[i] = 1，所以只要判断nums[i] == nums[i - 1] && markedArr[i] = 1就一定可以确定是同一层之间出现的重复，从而可以实现对同一层的去重。
如下面这个题目：
https://leetcode.cn/problems/combination-sum-ii/
解答代码：
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] markUsed;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);// 先排序方便剪枝
// 用一个标记数组来标记candidates数组中的元素是否在同一层中重复出现过,还是在同一个递归树枝中重复出现
// 在for循环中，遍历一次candidates[i]，就会把与之对应的markUsed[i]变为false,如果是同一层，必定会进行回溯
// markUsed[i]又变为true的操作，如果是递归进树枝的下一层，那么就不会进行回溯操作，所以可以用markUsed[i - 1]来判断前一个元素是在同一层中重复还是递归树枝中重复
markUsed = new boolean[candidates.length];
Arrays.fill(markUsed, false);
backtracking(candidates, target, 0, 0, markUsed);
return result;
}
private void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] markUsed) {
// 递归终止条件
if (sum > target) {
return;
}
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (i > 0 && candidates[i] == candidates[i - 1] && markUsed[i - 1] == false) {
continue;
}
if (sum + candidates[i] > target) {
break;// 如果选取数的一次for循环中，发现sum + candidates[i]已经大于target，那么后续候选的一定会更加大，所以for循环直接结束
}
path.add(candidates[i]);
sum += candidates[i];
markUsed[i] = true;
backtracking(candidates, target, sum, i + 1, markUsed);
path.remove(path.size() - 1);// 回溯
sum -= candidates[i];// 回溯
markUsed[i] = false;
}
}
}
b、当题目条件不允许进行排序的时候，就不能用上面的方法，这个时候要实现同一层去重可以考虑在每一层new一个标记数组即这个标记数组只负责一层的标记，在每一层中标记数组不进行回溯，但是进入递归下一层后所有的标记都会被清除掉，这样只会标记同一层重复出现的元素。
递增子序列
class Solution {
//
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums, 0);
return result;
}
private void backtracking(int[] nums, int startIndex) {
// 往下一层选元素的终止条件
if (path.size() >= 2) {
result.add(new ArrayList<>(path));
// 这里不需要return 因为要找出所有的子序列，只要满足条件的都需要加进来
}
if (startIndex == nums.length) {
return;// 可以不加，startIndex等于数组的长度时，自然也无法进入下一个的for循环来选元素
}
int [] markedArr = new int[201];
for (int i = startIndex; i < nums.length; i++) {
// 什么情况不加进path
// 有重复
if (markedArr[nums[i] + 100] == 1) {
continue;
}
// 待选的数比path中最后一个被选进去的数要小
if ( i > 0 && !path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
continue;
}
markedArr[nums[i] + 100] = 1;
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);// path需要回溯，但是markedArr数组不需要，她负责的是同一层的数字的标记
}
}
}
②对于排序的去重，分为两种情况：待选数组无重复和有重复。
a、待选数组无重复，只需考虑同一树枝的去重。
https://leetcode.cn/problems/permutations/
同一树枝的去重也是使用标记数组来映射待选取数组，但是映射的方式有两种：
Q1、一种是通过markedArr[nums.length]来一 一对应映射nums[i]；
class Solution {
// 全排列相当于放回选取，标记选过的元素，因为不含重复
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] markedArr;
// 去重包括两种情况：第一种是同一层去重，第二种是不同层去重；
// 同一层中出现重复的情况只可能是数组中本身就有重复的元素，本题明确数组不含重复数字，所有不用考虑同层的去重
// 而不同层出现重复的情况是题目的选取方式是组合还是排列（不放回和放回选取），反映在代码中是是否考虑在递归函数中引入一个整型的startIndex来代表组合还是排列
// 这个题是排列，所以不需要startIndex来调整下一层的起始位置
// 而排列的不同层去重就需要一个全局的标记数组来标记已经出现过的元素，因此在递归函数中引入一个参数int[] markedArr
// 并且每一层的排列都是从头开始选择数组中的元素，因此需要即使当数组中没有重复元素时，每一次的选择还是一定会出现重复的情况，如[1,2,3]中已选出2的情况，下一层是从头开始，依次选择1,2,3,这个情况下，在上一层已经选择了2的情况下这一层再次碰到2需要去重
// 一个全局变量的标记数组回溯是在同一层回溯，不会回溯掉上一层的选取元素，适合不同层之间的去重操作
// 同层去重操作有两个选择：①可以排序的话先排序，利用递归只作用于不同层的性质来操作标记数组，②不排序的话，每一层更新标记数组，那么数组只会标记在同一层重复的元素
// 这个题目是不含重复的数组全排列，那么不用考虑同层去重，因为是全排列所以需要考虑不同层之间的去重且不需要每一层更新选取得起点
public List<List<Integer>> permute(int[] nums) {
markedArr = new int[nums.length];
backtracking(nums, markedArr);
return result;
}
private void backtracking(int[] nums, int[] markedArr) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (markedArr[i] == 1) {
continue;
}
path.add(nums[i]);
// 标记元素
markedArr[i] = 1;
backtracking(nums, markedArr);
path.remove(path.size() - 1);
markedArr[i] = 0;// 同层之间回溯标记（取消标记），防止影响下一层的选取
}
}
}
Q2、第二种情况类似于map的底层原理，用markedArr[nums[i] + 10]来映射num[i]。
这两种情况的区别是——第一种方法可以通用，但是比后一种消耗更多的空间，第二种方法仅仅适用于元素只出现一次重复的情况，如果用于元素会出现两次的情况，那么就会多去重一个元素。
class Solution {
// 全排列相当于放回选取，标记选过的元素，因为不含重复
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] markedArr;
// 去重包括两种情况：第一种是同一层去重，第二种是不同层去重；
// 同一层中出现重复的情况只可能是数组中本身就有重复的元素，本题明确数组不含重复数字，所有不用考虑同层的去重
// 而不同层出现重复的情况是题目的选取方式是组合还是排列（不放回和放回选取），反映在代码中是是否考虑在递归函数中引入一个整型的startIndex来代表组合还是排列
// 这个题是排列，所以不需要startIndex来调整下一层的起始位置
// 而排列的不同层去重就需要一个全局的标记数组来标记已经出现过的元素，因此在递归函数中引入一个参数int[] markedArr
// 并且每一层的排列都是从头开始选择数组中的元素，因此需要即使当数组中没有重复元素时，每一次的选择还是一定会出现重复的情况，如[1,2,3]中已选出2的情况，下一层是从头开始，依次选择1,2,3,这个情况下，在上一层已经选择了2的情况下这一层再次碰到2需要去重
// 一个全局变量的标记数组回溯是在同一层回溯，不会回溯掉上一层的选取元素，适合不同层之间的去重操作
// 同层去重操作有两个选择：①可以排序的话先排序，利用递归只作用于不同层的性质来操作标记数组，②不排序的话，每一层更新标记数组，那么数组只会标记在同一层重复的元素
// 这个题目是不含重复的数组全排列，那么不用考虑同层去重，因为是全排列所以需要考虑不同层之间的去重且不需要每一层更新选取得起点
public List<List<Integer>> permute(int[] nums) {
markedArr = new int[21];
backtracking(nums, markedArr);
return result;
}
private void backtracking(int[] nums, int[] markedArr) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (markedArr[nums[i] + 10] == 1) {
continue;
}
path.add(nums[i]);
// 标记元素
markedArr[nums[i] + 10] = 1;
backtracking(nums, markedArr);
path.remove(path.size() - 1);
markedArr[nums[i] + 10] = 0;// 同层之间回溯标记（取消标记），防止影响下一层的选取
}
}
}
b、待选数组有重复，需要同时进行同一树层和同一树枝的去重（先对待选数组进行排序）
排列中待选数组有重复需要额外注意不要踩这种坑：因为排列中待选数组有重复的话会导致有一个元素势必在下一层至少重复出现2次以上，所以这个时候需要注意标记数组这个细节。需要使用一 一对应的标记数组来进行标记，不然会多去重。
注意这个注释：
// 不同层去重
// 不同层之间去重也分为两种情况：①待选数组没有重复的可以考虑用一个标记数组,用nums[i] + 10来映射标记数组的元素markedArr[nums[i] + 10]
// ②：用一个标记数组markedArr完完全全的，用markedArr[i]来对应nums[i]
// 但是①这种方法有一个缺点就是如果碰到了会出现元素重复出现两次以上的情况的话，就会多跳过一个元素，如本题的[1,1,2]，先选取第二个1，标记的是markedArr[11]为true,再下一层依次选择1,1,2，这个时候如果用上面说的方法就会把两个1都去掉，但是实际上我们只需要去掉第2个1就可以了，出现这种的原因是如果用nums[i] + 10来映射标记数组的元素markedArr[nums[i] + 10]，第一个1和第二个1映射的都是映射了markedArr[11]这个元素，那么后续只要碰到1，就会跳过，而题目nums数组中1出现了两次，因而势必会多去重了一个1
// 那么这个时候就要改进一下，不同层去重的第二种方法②：用一个标记数组markedArr完完全全的，用markedArr[i]来对应nums[i]，这样技术待选数组中有重复的元素，也不用担心会多去重一个，还是上面那个例子：[1,1,2]，当选取了第二个1时，标记的是markedArr[1]为，下一层一次选取1,1,2 ，虽然会重复两个1，但是重复的第一个1对应的是markedArr[0],重复的第二个1对应的是markedArr[1]，在不同层判断是否去重时，markedArr[0]为FALSE，不进入同一层去重的操作。
47. 全排列 II - 力扣（LeetCode）
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] markedArr;
public List<List<Integer>> permuteUnique(int[] nums) {
markedArr = new int[nums.length];
Arrays.sort(nums);// 同层之间去重选择之一需要排序
backtracking(nums, markedArr);
return result;
}
private void backtracking(int[] nums, int[] markedArr) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && markedArr[i - 1] == 0){
// 同层去重
continue;
}
// 不同层去重
// 不同层之间去重也分为两种情况：①待选数组没有重复的可以考虑用一个标记数组,用nums[i] + 10来映射标记数组的元素markedArr[nums[i] + 10]
// ②：用一个标记数组markedArr完完全全的，用markedArr[i]来对应nums[i]
// 但是①这种方法有一个缺点就是如果碰到了会出现元素重复出现两次以上的情况的话，就会多跳过一个元素，如本题的[1,1,2]，先选取第二个1，标记的是markedArr[11]为true,再下一层依次选择1,1,2，这个时候如果用上面说的方法就会把两个1都去掉，但是实际上我们只需要去掉第2个1就可以了，出现这种的原因是如果用nums[i] + 10来映射标记数组的元素markedArr[nums[i] + 10]，第一个1和第二个1映射的都是映射了markedArr[11]这个元素，那么后续只要碰到1，就会跳过，而题目nums数组中1出现了两次，因而势必会多去重了一个1
// 那么这个时候就要改进一下，不同层去重的第二种方法②：用一个标记数组markedArr完完全全的，用markedArr[i]来对应nums[i]，这样技术待选数组中有重复的元素，也不用担心会多去重一个，还是上面那个例子：[1,1,2]，当选取了第二个1时，标记的是markedArr[1]为，下一层一次选取1,1,2 ，虽然会重复两个1，但是重复的第一个1对应的是markedArr[0],重复的第二个1对应的是markedArr[1]，在不同层判断是否去重时，markedArr[0]为FALSE，不进入同一层去重的操作。
if (markedArr[i] == 1) {
continue;
}
markedArr[i] = 1;
path.add(nums[i]);
backtracking(nums, markedArr);
markedArr[i] = 0;
path.remove(path.size() - 1);
}
}
}