目录引入这三类题为什么总被放在一起一、全排列顺序不同就是不同答案二、子集每个数字只有选或不选三、子集异或总和不保存全部子集也能累计答案四、组合只向后选择消除顺序重复五、组合总和通过下一层参数决定能否重复使用六、全排列 II重复数字需要区分“同层”和“不同层”七、从多道题中归纳状态规律八、易错点九、本篇总结引入这三类题为什么总被放在一起排列、子集和组合都在枚举很多种可能答案所以代码中经常出现结果列表、当前选择列表和递归搜索。但它们的区别不在于有没有回溯而在于题目如何规定“顺序”和“能不能再次使用”。回溯可以理解成先做一个选择递归进入下一层递归返回后撤销刚才的选择再尝试同一层的其他选择。path是当前已经选中的数字列表ret是最终结果列表check[i]表示数组下标i的数字是否已经在当前排列中使用pos是当前处理的数组下标start是下一层允许开始选择的位置remain是组合总和题距离目标还差多少。一、全排列顺序不同就是不同答案题目描述题目全排列。LeetCode 46。给定一个不含重复数字的数组返回这些数字的所有排列。比如[1, 2, 3]中[1, 2, 3]和[2, 1, 3]是两个不同答案。题目链接全排列算法原理排列中的每一个位置都可以从整个数组中挑选数字但同一个数组下标在一条排列中不能重复使用。因此需要一个check布尔数组记录使用状态。当path.size()等于数组长度时一条完整排列形成。保存答案时要复制path因为递归返回后还会继续删除和添加其中的元素。Java 代码import java.util.ArrayList; import java.util.List; class Solution { ListListInteger ret; ListInteger path; boolean[] check; public ListListInteger permute(int[] nums) { ret new ArrayList(); path new ArrayList(); check new boolean[nums.length]; dfs(nums); return ret; } public void dfs(int[] nums) { if (nums.length path.size()) { ret.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (check[i] false) { path.add(nums[i]); check[i] true; dfs(nums); check[i] false; path.remove(path.size() - 1); } } } }代码说明path保存当前排列已经放入的数字check[i]表示nums[i]是否已经使用。每一层都遍历整个数组遇到已经使用的下标就跳过。递归返回后必须先把check[i]恢复为false再删除path的最后一个数字。这样下一条分支就回到了选择当前数字之前的状态。(回溯二、子集每个数字只有选或不选题目描述题目子集。LeetCode 78。给定一个不含重复元素的数组返回它的所有子集。空集也算一个子集元素的排列顺序不产生新的子集。题目链接子集算法原理子集题可以把每个数字看成一次二选一选择当前数字或者跳过当前数字。处理到数组下标pos时会产生两条递归分支下一层都处理pos 1。当pos到达数组长度时所有数字都已经做出决定把当前path复制到ret。因为每个数字都能选或不选所以空集自然会被枚举出来。Java 代码class Solution { ListListInteger ret; ListInteger path; public ListListInteger subsets(int[] nums) { ret new ArrayList(); path new ArrayList(); dfs(nums, 0); return ret; } public void dfs(int[] nums, int pos) { if (pos nums.length) { ret.add(new ArrayList(path)); return; } path.add(nums[pos]); dfs(nums, pos 1); path.remove(path.size() - 1); dfs(nums, pos 1); } }代码说明pos表示当前正在决定数组中的哪个位置。第一条分支把nums[pos]加到path表示选它递归返回后删除最后一个数字。第二条分支不修改path表示跳过它。和排列不同子集不需要check因为每个位置只会按从左到右被处理一次不存在回头选择的问题。三、子集异或总和不保存全部子集也能累计答案题目描述题目子集异或总和。LeetCode 1863。给定一个整数数组计算所有子集的按位异或总和。空集的异或结果按 0 计算。题目链接子集异或总和算法原理这道题仍然是在枚举每个数字“选或不选”但不要求返回所有子集因此不必维护ListInteger类型的path。path直接保存当前已经选中的数字进行异或后的结果sum保存所有分支结果的总和。每次进入dfs当前path都代表一个子集的异或结果所以先把它加入sum。循环从pos开始向后选择递归返回后再次异或同一个数字就能撤销刚才的异或选择。Java 代码class Solution { int path; int sum; public int subsetXORSum(int[] nums) { path 0; sum 0; dfs(nums, 0); return sum; } public void dfs(int[] nums, int pos) { sum path; for (int i pos; i nums.length; i) { path ^ nums[i]; dfs(nums, i 1); path ^ nums[i]; } } }代码说明^是 Java 的按位异或赋值运算。由于同一个数字异或两次会恢复原来的结果所以path ^ nums[i]可以作为选择和撤销选择的成对操作。这里的path不是数字列表而是当前子集的异或结果变量名虽然仍然叫path但理解它的实际含义更重要。pos限制后面的选择只能从当前下标之后开始因此不会重复枚举同一个子集。四、组合只向后选择消除顺序重复题目描述题目组合。LeetCode 77。给定两个整数n和k从1到n中选出k个数字返回所有可能的组合。组合中[1, 2]和[2, 1]视为同一种答案。题目链接组合算法原理组合不关心选择顺序因此可以规定数字只能从左到右选择。选择value后下一层从value 1开始后面不能再回到value之前。这种做法不需要check因为start已经把已经处理过的位置排除掉了。path.size() k时保存一份完整组合。Java 代码class Solution { public ListListInteger combine(int n, int k) { ListListInteger ret new ArrayList(); ListInteger path new ArrayList(); dfs(1, n, k, path, ret); return ret; } public void dfs(int start, int n, int k, ListInteger path, ListListInteger ret) { if (path.size() k) { ret.add(new ArrayList(path)); return; } for (int value start; value n; value) { path.add(value); dfs(value 1, n, k, path, ret); path.remove(path.size() - 1); } } }代码说明start是当前层允许选择的最小数字。第一层从 1 开始如果选择了 2下一层就从 3 开始因此不会生成[2, 1]这种回头选择。剪枝)new ArrayList(path)是复制当前路径。若直接把path放入ret后续的remove会改变之前保存的答案。五、组合总和通过下一层参数决定能否重复使用题目描述题目组合总和。LeetCode 39。给定一个无重复元素的整数数组candidates和目标整数target找出所有和为target的组合。同一个数字可以被无限次选取组合顺序不同但数字相同的结果只保留一种。题目链接组合总和算法原理remain表示距离目标和还剩多少。加入一个候选数字后剩余目标变成remain - candidates[i]。当remain 0时找到一个合法组合当remain 0时当前分支不可能再回到 0可以直接剪枝。因为本题允许重复使用当前数字所以递归下一层仍然传i而不是i 1。如果题目规定每个数字只能使用一次就应传i 1。Java 代码class Solution { public ListListInteger combinationSum(int[] candidates, int target) { ListListInteger ret new ArrayList(); dfs(0, target, candidates, new ArrayList(), ret); return ret; } public void dfs(int start, int remain, int[] candidates, ListInteger path, ListListInteger ret) { if (remain 0) { ret.add(new ArrayList(path)); return; } if (remain 0) return; for (int i start; i candidates.length; i) { path.add(candidates[i]); dfs(i, remain - candidates[i], candidates, path, ret); path.remove(path.size() - 1); } } }代码说明start让组合始终按候选数组向后搜索避免[2, 3]和[3, 2]被当成两种答案。remain小于 0 时直接返回是基于候选数字为正数这一条件进行的剪枝。本题最容易混淆的地方是递归参数dfs(i, ...)允许下一层再次选择candidates[i]dfs(i 1, ...)则表示当前数字用过后不能再用。六、全排列 II重复数字需要区分“同层”和“不同层”题目描述题目全排列 II。LeetCode 47。给定一个可能包含重复数字的数组返回所有不重复的排列。题目链接全排列 II算法原理先对数组排序让相同数字相邻。排列仍然需要check记录哪些下标已经使用但还要处理重复数字。如果当前数字和前一个数字相同并且前一个数字在当前层还没有被使用说明当前层已经尝试过同样的选择跳过当前数字。若前一个数字已经在当前路径中说明这是不同层的选择不能跳过否则会漏掉合法排列。Java 代码class Solution { ListListInteger ret; ListInteger path; boolean[] check; public ListListInteger permuteUnique(int[] nums) { Arrays.sort(nums); ret new ArrayList(); path new ArrayList(); check new boolean[nums.length]; dfs(nums); return ret; } public void dfs(int[] nums) { if (path.size() nums.length) { ret.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (check[i]) continue; if (i 0 nums[i] nums[i - 1] check[i - 1] false) { continue; } path.add(nums[i]); check[i] true; dfs(nums); path.remove(path.size() - 1); check[i] false; } } }代码说明Arrays.sort(nums)会把数组从小到大排序。Arrays是 Java 提供的数组工具类sort用于排序。判断check[i - 1] false的重点是“同一层”。如果前一个相同数字没有被当前路径使用当前候选和它会产生同层重复如果前一个数字已经在路径中则当前数字位于更深的一层仍然可能构成不同排列。七、从多道题中归纳状态规律排列、子集和组合的代码都在枚举选择但状态含义不同。排列关心顺序下一层仍然可以从整个数组寻找候选因此用check记录每个下标是否已经使用。子集对每个位置做“选或不选”用pos表示当前处理到哪里不需要check。组合不关心顺序使用start规定下一层只能向后选择。组合总和进一步用remain表示距离目标还差多少并根据是否允许重复决定传i还是i 1。含重复元素的排列还需要排序和同层去重。判断回溯题时最值得先问的是顺序是否重要元素能否重复使用输入是否有重复值答案是返回路径还是只统计数量这几个问题基本会决定check、pos、start和remain的写法。八、易错点排列误用start导致顺序不同的答案缺失。子集只保存非空路径漏掉空集。组合下一层仍传start造成重复选择或死循环。组合总和不清楚应该传i还是i 1。保存结果时直接保存path没有复制。check[i]标记后忘记恢复。含重复排列只判断相邻相等没有区分同一层和不同层。只为了套模板维护路径却忘记有些题可以直接累计答案。九、本篇总结这几类题的共同框架都是“选择、递归、撤销选择”真正决定题型的是下一层状态。排列用check管理使用情况子集用pos做二选一组合用start消除顺序重复组合总和用remain做目标剪枝。把这些变量的实际含义写清楚比死记方法名更容易在新题中恢复代码结构。