回溯算法解决排列—组合—子集问题
无论是排列、组合还是子集问题，就是让你从序列 nums 中以给定规则取若干元素，主要有以下几种变体：
-
元素无重不可复选，即
nums中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。 -
元素可重不可复选，即
nums中的元素可以存在重复，每个元素最多只能被使用一次。 -
元素无重可复选，即
nums中的元素都是唯一的，每个元素可以被使用若干次。 -
元素可重可复选。但既然元素可复选，那又何必存在重复元素呢元素去重之后就等同于形式三，所以这种情况不用考虑。
以上所说的问题都可以用这两棵树解决
组合问题和子集问题其实是等价的；至于之前说的三种变化形式，无非是在这两棵树上剪掉或者增加一些树枝罢了。
组合/子集问题
题目一:子集（元素无重不可复选）
题目：
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路：
求这一整棵树
我们通过保证元素之间的相对顺序不变来防止出现重复的子集，即：
dfs(i+1, nums);
Code:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0);
return res;
}
public void dfs(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.add(new LinkedList<>(list));
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 做选择
list.addLast(nums[i]);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
dfs(nums, i + 1);
// 撤销选择
list.removeLast();
}
}
}
题目二：组合（元素无重不可复选）
题目：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路：
求这棵树的一部分内容
Code:
public class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n, 1, k);
return res;
}
public void dfs(int n, int start, int k) {
// base case
if (list.size() == k) {
// 遍历到了第 k 层，收集当前节点的值
res.add(new LinkedList<>(list));
return;
}
for (int i = start; i <= n; i++) {
list.addLast(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
dfs(n, i + 1, k);
list.removeLast();
}
}
}
题目三：子集 II（元素可重不可复选）
题目：
给你一个整数数组nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
思路：
以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。
按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：
[
[],
[1],[2],[2'],
[1,2],[1,2'],[2,2'],
[1,2,2']
]
所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：
体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
Code:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
dfs(nums, 0);
return res;
}
public void dfs(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.add(new LinkedList<>(list));
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1])
continue;
// 做选择
list.addLast(nums[i]);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
dfs(nums, i + 1);
// 撤销选择
list.removeLast();
}
}
}
题目四：组合总和 II（元素可重不可复选）
题目：
给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次 。
注意：解集不能包含重复的组合。
思路：
同题目三
Code:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
int now = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 先排序，让相同的元素靠在一起
Arrays.sort(candidates);
dfs(candidates, target, 0);
return res;
}
public void dfs(int[] candidates, int target, int start) {
if (now == target) {
res.add(new LinkedList<>(list));
}
if (now > target)
return;
// 回溯算法标准框架
for (int i = start; i < candidates.length; i++) {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && candidates[i] == candidates[i - 1])
continue;
// 做选择
list.addLast(candidates[i]);
now += candidates[i];
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
dfs(candidates, target, i + 1);
// 撤销选择
list.removeLast();
now -= candidates[i];
}
}
}
题目五：组合总和（元素无重可复选）
题目：
给你一个 无重复元素 的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为target的不同组合数少于 150 个。
思路：
想解决这种类型的问题，也得回到回溯树上，我们不妨先思考思考，标准的子集/组合问题是如何保证不重复使用元素的？
答案在于 backtrack 递归时输入的参数 start：
// 无重组合的回溯算法框架
void backtrack(int[] nums, int start) {
for (int i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i + 1);
// ...
}
}
这个 i 从 start 开始，那么下一层回溯树就是从 start + 1 开始，从而保证 nums[start] 这个元素不会被重复使用：
那么反过来，如果我想让每个元素被重复使用，我只要把 i + 1 改成 i 即可：
// 可重组合的回溯算法框架
void backtrack(int[] nums, int start) {
for (int i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i);
// ...
}
}
这相当于给之前的回溯树添加了一条树枝，在遍历这棵树的过程中，一个元素可以被无限次使用：
当然，这样这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的base case以结束算法，即路径和大于 target 时就没必要再遍历下去了。
Code:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
int now = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates.length == 0)
return res;
dfs(candidates, target, 0);
return res;
}
public void dfs(int[] candidates, int target, int start) {
if (now == target) {
res.add(new LinkedList<>(list));
return;
}
if (now > target)
return;
// 回溯算法标准框架
for (int i = start; i < candidates.length; i++) {
// 做选择
list.addLast(candidates[i]);
now += candidates[i];
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
dfs(candidates, target, i);
// 撤销选择
list.removeLast();
now -= candidates[i];
}
}
}
排列问题
题目一：全排列（元素无重不可复选）
题目：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路：
组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。
但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择。
标准全排列可以抽象成如下这棵多叉树：
用 `used` 数组标记已经在路径上的元素避免重复选择，然后收集所有叶子节点上的值，就是所有全排列的结果：
Code:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
// list中的元素会被标记为 true
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
dfs(nums);
return res;
}
public void dfs(int[] nums) {
// base case，到达叶子节点
if (list.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList<>(list));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 已经存在 list 中的元素，不能重复选择
if (used[i])
continue;
// 做选择
list.addLast(nums[i]);
used[i] = true;
dfs(nums);
// 取消选择
list.removeLast();
used[i] = false;
}
}
}
题目二： 全排列 II （元素可重不可复选）
题目：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
思路：
假设输入为 nums = [1,2,2']，标准的全排列算法会得出如下答案：
[
[1,2,2'],[1,2',2],
[2,1,2'],[2,2',1],
[2',1,2],[2',2,1]
]
显然，这个结果存在重复，比如 [1,2,2'] 和 [1,2',2] 应该只被算作同一个排列，但被算作了两个不同的排列。
所以现在的关键在于，如何设计剪枝逻辑，把这种重复去除掉？
答案是，保证相同元素在排列中的相对位置保持不变。
比如说 nums = [1,2,2'] 这个例子，我保持排列中 2 一直在 2' 前面。
这样的话，你从上面 6 个排列中只能挑出 3 个排列符合这个条件：
[ [1,2,2'],[2,1,2'],[2,2',1] ]
这也就是正确答案。
进一步，如果 nums = [1,2,2',2'']，我只要保证重复元素 2 的相对位置固定，比如说 2 -> 2' -> 2''，也可以得到无重复的全排列结果。
仔细思考，应该很容易明白其中的原理：
标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
那么反映到代码上，你注意看这个剪枝逻辑：
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
// 如果前面的相邻相等元素没有用过，则跳过
continue;
}
// 选择 nums[i]
当出现重复元素时，比如输入 nums = [1,2,2',2'']，2' 只有在 2 已经被使用的情况下才会被选择，同理，2'' 只有在 2' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
Code：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> list = new LinkedList<>();
// list中的元素会被标记为 true
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used=new boolean[nums.length];
Arrays.sort(nums);
dfs(nums);
return res;
}
public void dfs(int[] nums) {
// base case，到达叶子节点
if (list.size() == nums.length) {
// 收集叶子节点上的值
res.add(new LinkedList<>(list));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// 已经存在 list 中的元素，不能重复选择
if (used[i])
continue;
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
continue;
// 做选择
list.addLast(nums[i]);
used[i] = true;
dfs(nums);
// 取消选择
list.removeLast();
used[i] = false;
}
}
}
排列(元素无重可复选)
力扣上没有类似的题目，我们不妨先想一下，nums 数组中的元素无重复且可复选的情况下，会有哪些排列？
比如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：
[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]
标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。
Code:
class Solution {
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) {
// base case，到达叶子节点
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();
}
}
}
总结：
形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrack 核心代码如下：
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 做选择
track.addLast(nums[i]);
// 注意参数
backtrack(nums, i + 1);
// 撤销选择
track.removeLast();
}
}
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 剪枝逻辑
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.addLast(nums[i]);
backtrack(nums);
// 撤销选择
track.removeLast();
used[i] = false;
}
}
形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrack 核心代码如下：
Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
// 回溯算法标准框架
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();
}
}
Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 剪枝逻辑
if (used[i]) {
continue;
}
// 剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
// 做选择
used[i] = true;
track.addLast(nums[i]);
backtrack(nums);
// 撤销选择
track.removeLast();
used[i] = false;
}
}
形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrack 核心代码如下：
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 做选择
track.addLast(nums[i]);
// 注意参数
backtrack(nums, i);
// 撤销选择
track.removeLast();
}
}
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 做选择
track.addLast(nums[i]);
backtrack(nums);
// 撤销选择
track.removeLast();
}
}