Leetcode|Leetcode --- 回溯算法系列1（秒杀组合、排列与子集） Leetcode---回溯算法系列1（秒杀

写在前先看一下回溯算法的套路模板，参考这里。
解决一个回溯问题，实际上就是一个【决策树的遍历过程】。你需要考虑三个问题：

路径：即已经做出的选择
选择列表：即当前还可以做出的选择
结束条件：到达决策树的底层，无法再做出选择条件

回溯的框架（伪代码）

result = [] void backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return// 避免栈溢出for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

【Leetcode|Leetcode --- 回溯算法系列1（秒杀组合、排列与子集）】框架的核心思想：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]][1]]`
保证当前已选列表（ramain）三种状态：

当前路径不满足，直接返回（注意判断，remain小于0）
到达底层，且满足，记录路径
路径继续搜索，进入for循环【做选择，递归（注意元素可重复选择），撤销选择】

代码：

private List> ans = new ArrayList<>(); public List> combinationSum(int[] candidates, int target){ backTrack(candidates, new ArrayList<>(), target, 0); return ans; }private void backTrack(int[] candidates, List 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.组合总和I（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], ]

思路分析：本题使用框架可以求解，但是这里需要说的是另一种优化思路：我们在进行遍历每个位置时，根据还没有填充位置的大小对待遍历的大小进行剪枝，即缩小可选列表的范围。
代码：

private List> ans = new ArrayList<>(); public List> combine(int n, int k) { backTrack(n, new ArrayList<>(), k, 1); return ans; }private void backTrack(int n, List 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 list, int k, int start) { if (k == list.size()) { ans.add(new ArrayList<>(list)); return; } // 剩余k - list.size()需要填，剩余剪枝 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> ans = new ArrayList<>(); public List> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); backTrack(candidates, new ArrayList<>(), target, 0); return new ArrayList<>(ans); }private void backTrack(int[] candidates, List 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的方案进行优化剪枝。
代码：

private List> ans = new ArrayList<>(); public List> combinationSum3(int k, int n) { int num = 9; backTrack(num, new ArrayList<>(), n, 1, k); return ans; }private void backTrack(int num, List 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] ]

思路分析：与T77类似，都是返回固定长度的数组。可以套用上述模板，加入元素前注意看该元素是否添加过，不再赘述。
这里介绍一种思路：通过以每个位置作start为起点，进递归前交换数组元素，出递归恢复数组。效率比较高！
代码：

private List> ans = new ArrayList<>(); public List> permute(int[] nums){ backTrack(nums, 0); return ans; } private void backTrack(int[] nums, int start) { if (start == nums.length) { List 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; }

6.全排列II（47-中）题目概述：给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
示例：

输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]

思路分析：与T46实现思路相同，不同点是数组含有重复元素。关键还是如何去重：因为含有重复元素，T40去重方法（会缩减结果数量）！！解决方案：我们可以使用hashset保存当前要交换的位置已经有过哪些元素了，如果存在（元素相同，索引不同）直接跳过。
代码：

private List> ans = new ArrayList<>(); public List> permuteUnique(int[] nums){ Arrays.sort(nums); backTrack(nums, 0); return ans; }private void backTrack(int[] nums, int start) { if (start == nums.length) { List list = new ArrayList<>(); for (int i : nums) { list.add(i); } ans.add(list); return; }HashSet 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> ans = new ArrayList<>(); public List> subsets(int[] nums) { backTrack(nums, new ArrayList<>(), 0); return ans; }private void backTrack(int[] nums, List 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> ans = new ArrayList<>(); public List> subsetsWithDup(int[] nums) { Arrays.sort(nums); backTrack(nums, new ArrayList<>(), 0); return ans; }private void backTrack(int[] nums, List 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); } }

总结我们可以发现上述题目可大致分为下列几种情况：