写在前
先看一下回溯算法的套路模板，参考这里。
解决一个回溯问题，实际上就是一个【决策树的遍历过程】。你需要考虑三个问题：
- 路径：即已经做出的选择
- 选择列表：即当前还可以做出的选择
- 结束条件：到达决策树的底层，无法再做出选择条件
回溯的框架（伪代码）
result = [] void backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return // 避免栈溢出 for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
框架的核心思想：for循环里边的递归，在递归调用之前做出选择，在递归调用之后撤销选择。
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
注意：但是可以根据情况进行剪枝减小时间复杂度。
1.组合总和（39-中）
题目概述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。注意：candidates 中的数字可以无限制重复被选取！！
示例：
输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
思路分析：同一元素可以使用多次（start定义可选择列表的起点），所以我们进入递归不能直接进入下一个元素，而是更新状态值，直到达到底层；注：相同数字不同排列视为一个结果！如[[1], [2]]和[[2], [1]]。
保证当前已选列表（ramain）三种状态：
- 当前路径不满足，直接返回（注意判断，remain小于0，剪枝）
- 到达底层，且满足，记录路径
- 路径继续搜索，进入for循环【做选择，递归（注意元素可重复选择），撤销选择】
代码：
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target){ backTrack(candidates, new ArrayList<>(), target, 0); return ans; } private void backTrack(int[] candidates, List<Integer> list, int remain, int start) { // 剪枝 if (remain < 0) return; else if (remain == 0) ans.add(new ArrayList<>(list)); else { for (int i = start; i < candidates.length; ++i) { list.add(candidates[i]); backTrack(candidates, list, remain - candidates[i], i); list.remove(list.size() - 1); } } }
2.组合（77-中）
题目概述：定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合，即相当于寻找数组[1, 2, ... n]的子数组，子数组大小为k。
注意：一个可能的结果中必须保证元素唯一性，即不能出现[1, 1]这种情况。
示例：
输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路分析：本题使用框架可以求解。与上题不同的是：一个元素只能用一次，且k为数组的个数，但是任然可以用dfs，终止条件是k = 0。
优化思路：更新搜索起点的上界。例如：如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了，这是因为：即使把 5 选上，后面的数只有 6 和 7，一共就 3 个候选数，凑不出 4 个数的组合。推导如下：
（1）搜索起点的上界 + 接下来要选择的元素个数 - 1 = n （2）接下来要选择的元素个数 = k - list.size() （3）搜索起点的上界：n - (k - list.size()) + 1
注意：起始位置是1，回溯的终止位置是n，都是闭区间。
代码：
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backTrack(n, new ArrayList<>(), k, 1); return ans; } private void backTrack(int n, List<Integer> list, int k, int start) { if (k == 0) { ans.add(new ArrayList<>(list)); return; } for (int i = start; i <= n; ++i) { list.add(i); backTrack(n, list, k - 1, i + 1); list.remove(list.size() - 1); } } // 剪枝优化后的回溯代码 private void backTrack(int n, List<Integer> list, int k, int start) { if (k == list.size()) { ans.add(new ArrayList<>(list)); return; } // 遍历搜索的起点位置（即起点上界） for (int i = start; i <= n - (k - list.size()) + 1; ++i) { list.add(i); backTrack(n, list, k, i + 1); list.remove(list.size() - 1); } }
3.组合总和II（40-中）
题目概述：给定一个数组 candidates （含有重复元素！！）和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次！！
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例：
输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
思路分析：与39题不同是：同一元素只用一次（start定义可选择列表的起点）但数组中含有相同元素；相同点是：相同数字列表的不同排列视为一个结果，如[[1], [2]]和[[2], [1]]。
本题关键是如何去掉结果的重复元素（由于数组中含有重复元素造成）。由于含有重复元素，我们要对数组进行排序，这很重要！去重有两种解决方案：
- 方案1：使用Set去重，由于底层是红黑树，效率过低。
- 方案2：通过索引确定重复元素，当前遍历索引大于起始可选列表，且元素相等（重复元素）！
代码实现：方案2
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { // 一定要先排序！ Arrays.sort(candidates); backTrack(candidates, new ArrayList<>(), target, 0); return new ArrayList<>(ans); } private void backTrack(int[] candidates, List<Integer> list, int remain, int start) { if (remain < 0) return; else if (remain == 0) { ans.add(new ArrayList<>(list)); return; } else { for (int i = start; i < candidates.length; ++i) { // 利用索引去重 if (i > start && candidates[i] == candidates[i - 1]) continue; list.add(candidates[i]); backTrack(candidates, list, remain - candidates[i], i + 1); list.remove(list.size() - 1); } } }
4.组合总和III（216-中）
题目概述：找出所有相加之和为 n 的 k个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。组合中元素唯一！
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例：
输入: k = 3, n = 7 输出: [[1,2,4]]
思路分析：该问题综合了前两个组合问题（重点），注意三点：
- 子数组含有k个元素，累加和为n，所以终止条件必须满足这两条！
- 数组元素唯一（1-9的整数），所以下一层递归的起始位置i + 1，数组内总长度为9，初始值为1，都是闭区间；
- 剪枝优化：（1）累加和remain<0，剪枝（2）剩余元素的个数不满足使用，剪枝！
代码：
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { int num = 9; backTrack(num, new ArrayList<>(), n, 1, k); return ans; } private void backTrack(int num, List<Integer> list, int remain, int start, int k) { if (remain < 0) return; else if (remain == 0 && k == list.size()) { ans.add(new ArrayList<>(list)); return; } // 剩余k - list.size()需要填充 for (int i = start; i <= num - (k - list.size()) + 1; ++i) { list.add(i); backTrack(num, list, remain - i, i + 1, k); list.remove(list.size() - 1); } }
5.全排列（46-中）
题目概述：给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路分析：与组合问题不同，一般解法如方案1，全排列起始位置是0。
方案1：在搜索得到所有排列的时候，需要记录当前排列已经选了哪些元素，需要数组记录一下，出递归需要将这个元素恢复。
方案2：比较巧妙，通过以每个位置作start为起点，进递归前交换数组元素，出递归恢复数组。每次固定一个元素，当start到达数组末尾时，我们得到排列的一种组合，遍历获取即可。效率比较高！
代码：
// 方案1 private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> permute(int[] nums){ int n = nums.length; boolean[] used = new boolean[n]; backTrack(nums, new ArrayList<>(), used); return ans; } private void backTrack(int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { ans.add(new ArrayList<>(path)); return; } // 在还未选择的数中选一个，作为排列的下一个值 for (int i = 0; i < nums.length; ++i) { if (!used[i]) { path.add(nums[i]); used[i] = true; backTrack(nums, path, used); used[i] = false; path.remove(path.size() - 1); } } } // 方案2：特别注意for循环的起始位置和起始位置的变动！ private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> permute(int[] nums){ backTrack(nums, 0); return ans; } private void backTrack(int[] nums, int start) { if (start == nums.length) { List<Integer> list = new ArrayList<>(); for (int i : nums) { list.add(i); } ans.add(list); return; } for (int i = start; i < nums.length; i++) { swap(nums, i, start); backTrack(nums, start + 1); swap(nums, i, start); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
拓展(T60)：排序序列，给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123" "132" "213" "231" "312" "321" 如： 输入：n = 3, k = 3 输出："213"
给定 n 和 k，返回第 k 个排列。
思路：待补充。。。
6.全排列II（47-中）
题目概述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
思路分析：与T46实现思路相同，不同点是数组含有重复元素。关键还是如何去重！
- 方案1：直接在加入判断是否出现过，没出现加入，效率极低。
- 方案2：先排序（前提），然后进行剪枝，比如112， 第一个1使用然后被撤销，剪的就是这部分。所以!used（i - 1），i - 1被撤销过，且没被使用，剪枝。
- 方案3：使用hashset保存当前要交换的位置已经有过哪些元素了，如果存在（元素相同，索引不同）直接跳过。
代码：
// 方案2 private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums){ int n = nums.length; boolean[] used = new boolean[n]; // 排序是前提 Arrays.sort(nums); backTrack(nums, new ArrayList<>(), used); return ans; } private void backTrack(int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { if (!ans.contains(path)) { ans.add(new ArrayList<>(path)); 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; } path.add(nums[i]); used[i] = true; backTrack(nums, path, used); used[i] = false; path.remove(path.size() - 1); } } // 方案3 private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums){ Arrays.sort(nums); backTrack(nums, 0); return ans; } private void backTrack(int[] nums, int start) { if (start == nums.length) { List<Integer> list = new ArrayList<>(); for (int i : nums) { list.add(i); } ans.add(list); return; } HashSet<Integer> set = new HashSet<>(); for (int i = start; i < nums.length; i++) { // 具有相同值的索引不交换，直接跳过 if (set.contains(nums[i])) continue; set.add(nums[i]); swap(nums, i, start); backTrack(nums, start + 1); swap(nums, i, start); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
7.子集（78-中）
题目概述：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集！你可以按 任意顺序 返回解集。
示例：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
思路分析：本题可以直接套用模板，每个元素只能使用一次!
注意：没有边界条件，直接添加到结果（任意一个都可能是子集，包括空集）。
代码：
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backTrack(nums, new ArrayList<>(), 0); return ans; } private void backTrack(int[] nums, List<Integer> list, int start) { ans.add(new ArrayList<>(list)); for (int i = start; i < nums.length; ++i) { list.add(nums[i]); backTrack(nums, list, i + 1); list.remove(list.size() - 1); } }
8.子集II（90-中）
题目概述：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。但解集不能包含重复的子集。
示例：
输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路分析：本题与T78思路相同，但含有重复元素。关键是去重，这里采用T40的去重方法。注意：排序是去重的前提！
代码：
private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); backTrack(nums, new ArrayList<>(), 0); return ans; } private void backTrack(int[] nums, List<Integer> list, int start) { ans.add(new ArrayList<>(list)); for (int i = start; i < nums.length; ++i) { if (i > start && nums[i] == nums[i - 1]) continue; list.add(nums[i]); backTrack(nums, list, i + 1); list.remove(list.size() - 1); } }
总结
我们可以发现上述题目可大致分为下列几种情况：
- 数组不含重复元素：T39组合数；T46全排列；T78子集
- 数组中含有重复元素：T40组合数II；T47全排列II；T90子集II
- 结果元素可重用性：不在举例说明
总结一些技巧：
- 对于限制累加和：注意分析当前
剩余值remain不同的状态，决定返回还是继续递归； - 对于限制子数组大小：注意在
for循环优化剪枝，当剩余元素个数小于限定数组大小（剪枝），终止条件：子数组长度list.size() == 目标长度k； - 对于含有重复元素：关键对数组进行排序
Arrays.sort()，然后优化剪枝（移动无关指针），这里还要区分[组合，子集]与[排列]去重的方法； - 对于全排列问题：优化方案通过交换索引
swap()，遍历每个排列状态（推荐）； - 对于当前元素可重用：下次递归选择还是从当前位置
i,否则从下一个位置i + 1开始。
ps：结果都必须保证相同数字列表的不同排列视为一个结果！
