回溯算法秒杀所有排列-组合-子集问题
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
———–
本文有视频版： 回溯算法秒杀所有排列/组合/子集问题。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
无论是排列、组合还是子集问题，简单说无非就是让你从序列 nums 中以给定规则取若干元素，主要有以下几种变体：
形式一、元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。
以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该只有 [7]。
形式二、元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次。
以组合为例，如果输入 nums = [2,5,2,1,2]，和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。
形式三、元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次。
以组合为例，如果输入 nums = [2,3,6,7]，和为 7 的组合应该有两种 [2,2,3] 和 [7]。
当然，也可以说有第四种形式，即元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。
上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。
除此之外，题目也可以再添加各种限制条件，比如让你求和为 target 且元素个数为 k 的组合，那这么一来又可以衍生出一堆变体，怪不得面试笔试中经常考到排列组合这种基本题型。
但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。
具体来说，你需要先阅读并理解前文 回溯算法核心套路，然后记住如下子集问题和排列问题的回溯树，就可以解决所有排列组合子集相关的问题：
为什么只要记住这两种树形结构就能解决所有相关问题呢？
首先，组合问题和子集问题其实是等价的，这个后面会讲；至于之前说的三种变化形式，无非是在这两棵树上剪掉或者增加一些树枝罢了。
那么，接下来我们就开始穷举，把排列/组合/子集问题的 9 种形式都过一遍，学学如何用回溯算法把它们一套带走。
子集（元素无重不可复选）
力扣第 78 题「 子集」就是这个问题：
题目给你输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集。
函数签名如下：
List<List<Integer>> subsets(int[] nums)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<vector<int>> subsets(vector<int>& nums)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def subsets(nums: List[int]) -> List[List[int]]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func subsets(nums []int) [][]int
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
function subsets(nums) {
// function body goes here
}
比如输入 nums = [1,2,3]，算法应该返回如下子集：
[ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]
好，我们暂时不考虑如何用代码实现，先回忆一下我们的高中知识，如何手推所有子集？
首先，生成元素个数为 0 的子集，即空集 []，为了方便表示，我称之为 S_0。
然后，在 S_0 的基础上生成元素个数为 1 的所有子集，我称为 S_1：
接下来，我们可以在 S_1 的基础上推导出 S_2，即元素个数为 2 的所有子集：
为什么集合 [2] 只需要添加 3，而不添加前面的 1 呢？
因为集合中的元素不用考虑顺序，[1,2,3] 中 2 后面只有 3，如果你添加了前面的 1，那么 [2,1] 会和之前已经生成的子集 [1,2] 重复。
换句话说，我们通过保证元素之间的相对顺序不变来防止出现重复的子集。
接着，我们可以通过 S_2 推出 S_3，实际上 S_3 中只有一个集合 [1,2,3]，它是通过 [1,2] 推出的。
整个推导过程就是这样一棵树：
注意这棵树的特性：
如果把根节点作为第 0 层，将每个节点和根节点之间树枝上的元素作为该节点的值，那么第 n 层的所有节点就是大小为 n 的所有子集。
你比如大小为 2 的子集就是这一层节点的值：
注意，本文之后所说「节点的值」都是指节点和根节点之间树枝上的元素，且将根节点认为是第 0 层。
直接看代码：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// 主函数
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return res;
}
// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.add(new LinkedList<>(track));
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 做选择
track.addLast(nums[i]);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(nums, i + 1);
// 撤销选择
track.removeLast();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
private:
vector<vector<int>> res;
// 记录回溯算法的递归路径
vector<int> track;
public:
// 主函数
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return res;
}
// 回溯算法核心函数，遍历子集问题的回溯树
void backtrack(vector<int>& nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.push_back(track);
// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
// 做选择
track.push_back(nums[i]);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(nums, i + 1);
// 撤销选择
track.pop_back();
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
def __init__(self):
self.res = []
# 记录回溯算法的递归路径
self.track = []
# 主函数
def subsets(self, nums: List[int]) -> List[List[int]]:
self.backtrack(nums, 0)
return self.res
# 回溯算法核心函数，遍历子集问题的回溯树
def backtrack(self, nums: List[int], start: int) -> None:
# 前序位置，每个节点的值都是一个子集
self.res.append(list(self.track))
# 回溯算法标准框架
for i in range(start, len(nums)):
# 做选择
self.track.append(nums[i])
# 通过 start 参数控制树枝的遍历，避免产生重复的子集
self.backtrack(nums, i + 1)
# 撤销选择
self.track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func subsets(nums []int) [][]int {
res := [][]int{}
track := []int{}
// 定义回溯函数
var backtrack func(start int)
backtrack = func(start int) {
// 每次加入一个子集
temp := make([]int, len(track))
copy(temp, track)
res = append(res, temp)
// 回溯算法框架
for i := start; i < len(nums); i++ {
// 做出选择
track = append(track, nums[i])
// 递归进入下一个状态
backtrack(i+1)
// 撤销上一个状态
track = track[:len(track)-1]
}
}
backtrack(0)
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
// 用于存储结果
const res = [];
// 用于记录回溯路径
const track = [];
/**
* 回溯算法的核心函数，用于遍历子集问题的回溯树
* @param {number} start - 控制树枝的遍历，避免产生重复子集
*/
const backtrack = (start) => {
// 前序遍历位置，每个节点的值都是一个子集
res.push([...track]);
// 回溯算法标准框架
for (let i = start; i < nums.length; i++) {
// 做选择
track.push(nums[i]);
// 回溯遍历下一层节点
backtrack(i + 1);
// 撤销选择
track.pop();
}
};
backtrack(0);
return res;
};
看过前文
回溯算法核心框架 的读者应该很容易理解这段代码吧，我们使用 start 参数控制树枝的生长避免产生重复的子集，用 track 记录根节点到每个节点的路径的值，同时在前序位置把每个节点的路径值收集起来，完成回溯树的遍历就收集了所有子集：
最后，backtrack 函数开头看似没有 base case，会不会进入无限递归？
其实不会的，当 start == nums.length 时，叶子节点的值会被装入 res，但 for 循环不会执行，也就结束了递归。
🌈 代码可视化动画 🌈
组合（元素无重不可复选）
如果你能够成功的生成所有无重子集，那么你稍微改改代码就能生成所有无重组合了。
你比如说，让你在 nums = [1,2,3] 中拿 2 个元素形成所有的组合，你怎么做？
稍微想想就会发现，大小为 2 的所有组合，不就是所有大小为 2 的子集嘛。
所以我说组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。
比如力扣第 77 题「 组合」：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
函数签名如下：
List<List<Integer>> combine(int n, int k)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<vector<int>> combine(int n, int k)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def combine(n: int, k: int) -> List[List[int]]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func combine(n int, k int) [][]int
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var combine = function (n, k) {
// function body
};
比如 combine(3, 2) 的返回值应该是：
[ [1,2],[1,3],[2,3] ]
这是标准的组合问题，但我给你翻译一下就变成子集问题了：
给你输入一个数组 nums = [1,2..,n] 和一个正整数 k，请你生成所有大小为 k 的子集。
还是以 nums = [1,2,3] 为例，刚才让你求所有子集，就是把所有节点的值都收集起来；现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：
反映到代码上，只需要稍改 base case，控制算法仅仅收集第 k 层节点的值即可：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// 主函数
public List<List<Integer>> combine(int n, int k) {
backtrack(1, n, k);
return res;
}
void backtrack(int start, int n, int k) {
// base case
if (k == track.size()) {
// 遍历到了第 k 层，收集当前节点的值
res.add(new LinkedList<>(track));
return;
}
// 回溯算法标准框架
for (int i = start; i <= n; i++) {
// 选择
track.addLast(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i + 1, n, k);
// 撤销选择
track.removeLast();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
public:
vector<vector<int>> res;
// 记录回溯算法的递归路径
deque<int> track;
// 主函数
vector<vector<int>> combine(int n, int k) {
backtrack(1, n, k);
return res;
}
void backtrack(int start, int n, int k) {
// base case
if (k == track.size()) {
// 遍历到了第 k 层，收集当前节点的值
res.push_back(vector<int>(track.begin(), track.end()));
return;
}
// 回溯算法标准框架
for (int i = start; i <= n; i++) {
// 选择
track.push_back(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i + 1, n, k);
// 撤销选择
track.pop_back();
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
def __init__(self):
self.res = []
# 记录回溯算法的递归路径
self.track = []
# 主函数
def combine(self, n: int, k: int) -> List[List[int]]:
self.backtrack(1, n, k)
return self.res
def backtrack(self, start: int, n: int, k: int) -> None:
# base case
if k == len(self.track):
# 遍历到了第 k 层，收集当前节点的值
self.res.append(self.track.copy())
return
# 回溯算法标准框架
for i in range(start, n+1):
# 选择
self.track.append(i)
# 通过 start 参数控制树枝的遍历，避免产生重复的子集
self.backtrack(i + 1, n, k)
# 撤销选择
self.track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func combine(n int, k int) [][]int {
res := [][]int{}
// 记录回溯算法的递归路径
track := []int{}
backtrack(1, n, k, &res, &track)
return res
}
func backtrack(start int, n int, k int, res *[][]int, track *[]int) {
// base case
if k == len(*track) {
// 遍历到了第 k 层，收集当前节点的值
temp := make([]int, len(*track))
copy(temp, *track)
*res = append(*res, temp)
return
}
// 回溯算法标准框架
for i := start; i <= n; i++ {
// 选择
*track = append(*track, i)
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i+1, n, k, res, track)
// 撤销选择
*track = (*track)[:len(*track)-1]
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
const res = [];
const track = [];
// 主函数
function backtrack(start, n, k) {
// base case
if (k === track.length) {
// 遍历到了第 k 层，收集当前节点的值
res.push([...track]);
return;
}
// 回溯算法标准框架
for (let i = start; i <= n; i++) {
// 选择
track.push(i);
// 通过 start 参数控制树枝的遍历，避免产生重复的子集
backtrack(i + 1, n, k);
// 撤销选择
track.pop();
}
}
backtrack(1, n, k);
return res;
};
这样，标准的子集问题也解决了。
🌟 代码可视化动画 🌟
排列（元素无重不可复选）
排列问题在前文 回溯算法核心框架 讲过，这里就简单过一下。
力扣第 46 题「 全排列」就是标准的排列问题：
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
函数签名如下：
List<List<Integer>> permute(int[] nums)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<vector<int>> permute(vector<int>& nums)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
def permute(nums: List[int]) -> List[List[int]]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func permute(nums []int) [][]int {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var permute = function(nums) {}
比如输入 nums = [1,2,3]，函数的返回值应该是：
[
[1,2,3],[1,3,2],
[2,1,3],[2,3,1],
[3,1,2],[3,2,1]
]
刚才讲的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。
但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择。
标准全排列可以抽象成如下这棵多叉树：
我们用 used 数组标记已经在路径上的元素避免重复选择，然后收集所有叶子节点上的值，就是所有全排列的结果：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯算法的递归路径
LinkedList<Integer> track = new LinkedList<>();
// track 中的元素会被标记为 true
boolean[] used;
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
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 中的元素，不能重复选择
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.addLast(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.removeLast();
used[i] = false;
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
public:
// 存储所有排列结果的列表
vector<vector<int>> res;
// 记录回溯算法的递归路径
list<int> track;
// 标记数字使用状态的数组，0 表示未被使用，1 表示已被使用
bool* used;
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
vector<vector<int>> permute(vector<int>& nums) {
used = new bool[nums.size()]();
// 满足回溯框架时需要添加 bool 类型默认初始化为 false
backtrack(nums);
return res;
}
// 回溯算法核心函数
void backtrack(vector<int>& nums) {
// base case，到达叶子节点
if (track.size() == nums.size()) {
// 收集叶子节点上的值
res.push_back(vector<int>(track.begin(), track.end()));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.size(); i++) {
// 已经存在 track 中的元素，不能重复选择
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.push_back(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.pop_back();
used[i] = false;
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
res = []
#记录回溯算法的递归路径
track = []
# track 中的元素会被标记为 true
used = []
# 主函数，输入一组不重复的数字，返回它们的全排列
def permute(self, nums: List[int]) -> List[List[int]]:
self.used = [False] * len(nums)
self.backtrack(nums)
return self.res
# 回溯算法核心函数
def backtrack(self, nums):
# base case，到达叶子节点
if len(self.track) == len(nums):
# 收集叶子节点上的值
self.res.append(self.track[:])
return
# 回溯算法标准框架
for i in range(len(nums)):
# 已经存在 track 中的元素，不能重复选择
if self.used[i]:
continue
# 做选择
self.used[i] = True
self.track.append(nums[i])
# 进入下一层回溯树
self.backtrack(nums)
# 取消选择
self.track.remove(nums[i])
self.used[i] = False
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func permute(nums []int) [][]int {
res := make([][]int, 0)
track := make([]int, 0)
used := make([]bool, len(nums))
backtrack(&res, &track, nums, used)
return res
}
func backtrack(res *[][]int, track *[]int, nums []int, used []bool) {
// base case，到达叶子节点
if len(*track) == len(nums) {
// 收集叶子节点上的值
tmp := make([]int, len(*track))
copy(tmp, *track)
*res = append(*res, tmp)
return
}
// 回溯算法标准框架
for i := 0; i < len(nums); i++ {
// 已经存在 track 中的元素，不能重复选择
if used[i] {
continue
}
// 做选择
used[i] = true
*track = append(*track, nums[i])
// 进入下一层回溯树
backtrack(res, track, nums, used)
// 取消选择
*track = (*track)[:len(*track)-1]
used[i] = false
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 记录回溯算法的递归路径
const track = [];
// track 中的元素会被标记为 true
let used;
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
var permute = function(nums) {
used = new Array(nums.length).fill(false);
backtrack(nums);
return res;
};
const res = [];
// 回溯算法核心函数
function backtrack(nums) {
// base case，到达叶子节点
if (track.length === nums.length) {
// 收集叶子节点上的值
res.push([...track]);
return;
}
// 回溯算法标准框架
for (let i = 0; i < nums.length; i++) {
// 已经存在 track 中的元素，不能重复选择
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.push(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.pop();
used[i] = false;
}
}
🥳 代码可视化动画 🥳
这样，全排列问题就解决了。
但如果题目不让你算全排列，而是让你算元素个数为 k 的排列，怎么算？
也很简单，改下 backtrack 函数的 base case，仅收集第 k 层的节点值即可：
// 回溯算法核心函数
void backtrack(int[] nums, int k) {
// base case，到达第 k 层，收集节点的值
if (track.size() == k) {
// 第 k 层节点的值就是大小为 k 的排列
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.length; i++) {
// ...
backtrack(nums, k);
// ...
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 回溯算法核心函数
void backtrack(vector<int>& nums, int k, vector<vector<int>>& res, vector<int>& track) {
// base case，到达第 k 层，收集节点的值
if (track.size() == k) {
// 第 k 层节点的值就是大小为 k 的排列
res.push_back(track);
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.size(); i++) {
// ...
backtrack(nums, k, res, track);
// ...
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 回溯算法核心函数
def backtrack(nums: List[int], k: int) -> None:
# base case，到达第 k 层，收集节点的值
if len(track) == k:
# 第 k 层节点的值就是大小为 k 的排列
res.append(track[:])
return
# 回溯算法标准框架
for i in range(len(nums)):
# ...
backtrack(nums, k)
# ...
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func backtrack(nums []int, k int) {
// base case，到达第 k 层，收集节点的值
if len(track) == k {
// 第 k 层节点的值就是大小为 k 的排列
res = append(res, append([]int(nil), track...))
return
}
// 回溯算法标准框架
for i := 0; i < len(nums); i++ {
// ...
backtrack(nums, k)
// ...
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 回溯算法核心函数
var backtrack = function(nums, k) {
// base case，到达第 k 层，收集节点的值
if (track.size() == k) {
// 第 k 层节点的值就是大小为 k 的排列
res.add(new LinkedList(track));
return;
}
// 回溯算法标准框架
for (var i = 0; i < nums.length; i++) {
// ...
backtrack(nums, k);
// ...
}
};
子集/组合（元素可重不可复选）
刚才讲的标准子集问题输入的 nums 是没有重复元素的，但如果存在重复元素，怎么处理呢？
力扣第 90 题「 子集 II」就是这样一个问题：
给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集。
函数签名如下：
List<List<Integer>> subsetsWithDup(int[] nums)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<vector<int>> subsetsWithDup(vector<int>& nums)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def subsetsWithDup(nums: List[int]) -> List[List[int]]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func subsetsWithDup(nums []int) [][]int
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var subsetsWithDup = function(nums) {
}
比如输入 nums = [1,2,2]，你应该输出：
[ [],[1],[2],[1,2],[2,2],[1,2,2] ]
当然，按道理说「集合」不应该包含重复元素的，但既然题目这样问了，我们就忽略这个细节吧，仔细思考一下这道题怎么做才是正事。
就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。
按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：
[
[],
[1],[2],[2'],
[1,2],[1,2'],[2,2'],
[1,2,2']
]
你可以看到，[2] 和 [1,2] 这两个结果出现了重复，所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：
体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int start) {
// 前序位置，每个节点的值都是一个子集
res.add(new LinkedList<>(track));
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();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
vector<vector<int>> res; // 输出结果
vector<int> track; // 搜索路径
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序，让相同的元素靠在一起
backtrack(nums, 0);
return res; // 返回结果
}
void backtrack(vector<int>& nums, int start) { // start 为当前的枚举位置
res.emplace_back(track); // 前序位置，每个节点的值都是一个子集
for(int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) { // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
continue;
}
track.emplace_back(nums[i]); // 添加至路径
backtrack(nums, i + 1); // 进入下一层决策树
track.pop_back(); // 回溯
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
def __init__(self):
# 用来存储结果的列表
self.res = []
# 用来存储当前走过的路径
self.track = []
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
# 对给定的数组进行排序，这样相同的元素就会排在一起。
nums.sort()
# 对数组进行回溯
self._backtrack(nums, 0)
return self.res
def _backtrack(self, nums, start):
# 前序位置，每个节点的值都是一个子集
self.res.append(self.track[:])
# 从start开始遍历nums数组
for i in range(start, len(nums)):
# 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if i > start and nums[i] == nums[i-1]:
continue
# 把当前数值添加到走过的路径列表中
self.track.append(nums[i])
# 从下一个数字的位置继续回溯
self._backtrack(nums, i+1)
# 回溯过程中要把当前数值从走过的路径中移除
self.track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func subsetsWithDup(nums []int) [][]int {
res := make([][]int, 0)
track := make([]int, 0)
// 先排序，让相同的元素靠在一起
sort.Ints(nums)
backtrack(nums, &track, &res, 0)
return res
}
func backtrack(nums []int, track *[]int, res *[][]int, start int) {
// 前序位置，每个节点的值都是一个子集
tmp := make([]int, len(*track))
copy(tmp, *track)
*res = append(*res, tmp)
for i := start; i < len(nums); i++ {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if i > start && nums[i] == nums[i-1] {
continue
}
*track = append(*track, nums[i])
backtrack(nums, track, res, i+1)
*track = (*track)[:len(*track)-1]
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var subsetsWithDup = function(nums) {
// 定义结果数组和回溯时的路径数组
let res = [];
let track = [];
// 排序，以便于剪枝算法的实现
nums.sort((a, b) => a - b);
// 回溯算法
const backtrack = (nums, start) => {
// 前序位置，每个节点的值都是一个子集
res.push([...track]);
// 遍历子集树枝
for (let i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
// 选择当前元素，加入路径数组
track.push(nums[i]);
// 向子节点递归
backtrack(nums, i + 1);
// 回溯，撤销选择
track.pop();
}
}
backtrack(nums, 0);
return res;
};
这段代码和之前标准的子集问题的代码几乎相同，就是添加了排序和剪枝的逻辑。
至于为什么要这样剪枝，结合前面的图应该也很容易理解，这样带重复元素的子集问题也解决了。
我们说了组合问题和子集问题是等价的，所以我们直接看一道组合的题目吧，这是力扣第 40 题「 组合总和 II」：
给你输入 candidates 和一个目标和 target，从 candidates 中找出中所有和为 target 的组合。
candidates 可能存在重复元素，且其中的每个数字最多只能使用一次。
说这是一个组合问题，其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。
所以这题怎么做呢？
对比子集问题的解法，只要额外用一个 trackSum 变量记录回溯路径上的元素和，然后将 base case 改一改即可解决这道题：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的元素之和
int trackSum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates.length == 0) {
return res;
}
// 先排序，让相同的元素靠在一起
Arrays.sort(candidates);
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
// base case，达到目标和，找到符合条件的组合
if (trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
// base case，超过目标和，直接结束
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// 做选择
track.add(nums[i]);
trackSum += nums[i];
// 递归遍历下一层回溯树
backtrack(nums, i + 1, target);
// 撤销选择
track.removeLast();
trackSum -= nums[i];
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
public:
vector<vector<int>> res;
//记录回溯的路径
vector<int> track;
//记录 track 中的元素之和
int trackSum = 0;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 先排序，让相同的元素靠在一起
sort(candidates.begin(), candidates.end());
backtrack(candidates, 0, target);
return res;
}
//回溯算法主函数
void backtrack(vector<int>& nums, int start, int target) {
//base case，达到目标和，找到符合条件的组合
if(trackSum == target) {
res.push_back(track);
return;
}
//base case，超过目标和，直接结束
if(trackSum > target) {
return;
}
//回溯算法标准框架
for(int i = start; i < nums.size(); i++) {
//剪枝逻辑，值相同的树枝，只遍历第一条
if(i > start && nums[i] == nums[i-1]) {
continue;
}
//做选择
track.push_back(nums[i]);
trackSum += nums[i];
//递归遍历下一层回溯树
backtrack(nums, i+1, target);
//撤销选择
track.pop_back();
trackSum -= nums[i];
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution:
def __init__(self):
self.res = []
# 记录回溯的路径
self.track = []
# 记录 track 中的元素之和
self.trackSum = 0
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return self.res
# 先排序，让相同的元素靠在一起
candidates.sort()
self.backtrack(candidates, 0, target)
return self.res
# 回溯算法主函数
def backtrack(self, nums: List[int], start: int, target: int):
# base case，达到目标和，找到符合条件的组合
if self.trackSum == target:
self.res.append(self.track[:])
return
# base case，超过目标和，直接结束
if self.trackSum > target:
return
# 回溯算法标准框架
for i in range(start, len(nums)):
# 剪枝逻辑，值相同的树枝，只遍历第一条
if i > start and nums[i] == nums[i - 1]:
continue
# 做选择
self.track.append(nums[i])
self.trackSum += nums[i]
# 递归遍历下一层回溯树
self.backtrack(nums, i + 1, target)
# 撤销选择
self.track.pop()
self.trackSum -= nums[i]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的元素之和
int trackSum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates.length == 0) {
return res;
}
// 先排序，让相同的元素靠在一起
Arrays.sort(candidates);
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
// base case，达到目标和，找到符合条件的组合
if (trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
// base case，超过目标和，直接结束
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// 做选择
track.add(nums[i]);
trackSum += nums[i];
// 递归遍历下一层回溯树
backtrack(nums, i + 1, target);
// 撤销选择
track.removeLast();
trackSum -= nums[i];
}
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var combinationSum2 = function(candidates, target) {
let res = [];
let track = [];
let trackSum = 0;
let sortedCandidates = candidates.sort((a, b) => a - b); // 排序
// 回溯函数
const backtrack = (nums, start, target) => {
// 达到目标和，找到符合条件的组合，记录结果
if (trackSum === target) {
res.push([...track]);
return;
}
// 先剪枝，超过目标和，直接结束
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (let i = start; i < nums.length; i++) {
// 剪枝逻辑，值相同的树枝，只遍历第一条
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
// 做选择
track.push(nums[i]);
trackSum += nums[i];
// 递归遍历下一层回溯树
backtrack(nums, i + 1, target);
// 撤销选择
track.pop();
trackSum -= nums[i];
}
}
backtrack(sortedCandidates, 0, target);
return res;
};
🌟 代码可视化动画 🌟
排列（元素可重不可复选）
排列问题的输入如果存在重复，比子集/组合问题稍微复杂一点，我们看看力扣第 47 题「 全排列 II」：
给你输入一个可包含重复数字的序列 nums，请你写一个算法，返回所有可能的全排列，函数签名如下：
List<List<Integer>> permuteUnique(int[] nums)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<vector<int>> permuteUnique(vector<int>& nums)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def permuteUnique(nums: List[int]) -> List[List[int]]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func permuteUnique(nums []int) [][]int
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var permuteUnique = function(nums) {
// code goes here
}
比如输入 nums = [1,2,2]，函数返回：
[ [1,2,2],[2,1,2],[2,2,1] ]
先看解法代码：
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
// 先排序，让相同的元素靠在一起
Arrays.sort(nums);
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
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;
}
track.add(nums[i]);
used[i] = true;
backtrack(nums);
track.removeLast();
used[i] = false;
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
public:
// 保存结果
vector<vector<int>> res;
// 记录当前位置的元素
vector<int> track;
// 记录元素是否被使用
vector<bool> used;
// 主函数
vector<vector<int>> permuteUnique(vector<int>& nums) {
// 排序，让相同的元素靠在一起
sort(nums.begin(), nums.end());
// 初始化used数组
used = vector<bool>(nums.size(), false);
// 回溯
backtrack(nums);
// 返回结果
return res;
}
// 回溯函数
void backtrack(vector<int>& nums) {
// 当长度相等时，将结果记录
if (track.size() == nums.size()) {
res.push_back(track);
return;
}
// 遍历没有被使用过的元素
for (int i = 0; i < nums.size(); i++) {
if (used[i]) {
continue;
}
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
// 添加元素，标记为使用过
track.push_back(nums[i]);
used[i] = true;
// 继续回溯
backtrack(nums);
// 回溯
track.pop_back();
used[i] = false;
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
res = [] # 用于存储结果
track = [] # 用于存储路径
used = [] # 记录元素是否使用过
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 先排序，让相同的元素靠在一起
nums.sort()
self.used = [False] * len(nums)
self.backtrack(nums)
return self.res
def backtrack(self, nums):
if len(self.track) == len(nums):
self.res.append(self.track.copy())
return
for i in range(len(nums)):
if self.used[i]:
continue
# 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
continue
self.track.append(nums[i])
self.used[i] = True
self.backtrack(nums)
self.track.pop()
self.used[i] = False
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func permuteUnique(nums []int) [][]int {
var res [][]int
var track []int
used := make([]bool, len(nums))
var backtrack func(nums []int)
// 全排列的基础模板，可以先参照第 46 题「全排列」
backtrack = func(nums []int) {
if len(track) == len(nums) {
tmp := make([]int, len(track))
copy(tmp, track)
res = append(res, tmp)
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
track = append(track, nums[i])
used[i] = true
backtrack(nums)
track = track[:len(track)-1]
used[i] = false
}
}
// 首先排序这个数组
sort.Ints(nums)
backtrack(nums)
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
let res = [];
let track = [];
let used = new Array(nums.length).fill(false);
// 先排序，让相同的元素靠在一起
nums.sort((a, b) => a - b);
backtrack(nums, used, track, res);
return res;
};
/**
* @param {number[]} nums
* @param {boolean[]} used
* @param {number[]} track
* @param {number[][]} res
*/
function backtrack(nums, used, track, res) {
if (track.length === nums.length) {
res.push(track.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
continue;
}
track.push(nums[i]);
used[i] = true;
backtrack(nums, used, track, res);
track.pop();
used[i] = false;
}
}
你对比一下之前的标准全排列解法代码，这段解法代码只有两处不同：
1、对 nums 进行了排序。
2、添加了一句额外的剪枝逻辑。
类比输入包含重复元素的子集/组合问题，你大概应该理解这么做是为了防止出现重复结果。
但是注意排列问题的剪枝逻辑，和子集/组合问题的剪枝逻辑略有不同：新增了 !used[i - 1] 的逻辑判断。
这个地方理解起来就需要一些技巧性了，且听我慢慢到来。为了方便研究，依然把相同的元素用上标 ' 以示区别。
假设输入为 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' 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。
这里拓展一下，如果你把上述剪枝逻辑中的 !used[i - 1] 改成 used[i - 1]，其实也可以通过所有测试用例，但效率会有所下降，这是为什么呢？
之所以这样修改不会产生错误，是因为这种写法相当于维护了 2'' -> 2' -> 2 的相对顺序，最终也可以实现去重的效果。
但为什么这样写效率会下降呢？因为这个写法剪掉的树枝不够多。
比如输入 nums = [2,2',2'']，产生的回溯树如下：
如果用绿色树枝代表 backtrack 函数遍历过的路径，红色树枝代表剪枝逻辑的触发，那么 !used[i - 1] 这种剪枝逻辑得到的回溯树长这样：
而 used[i - 1] 这种剪枝逻辑得到的回溯树如下：
可以看到，!used[i - 1] 这种剪枝逻辑剪得干净利落，而 used[i - 1] 这种剪枝逻辑虽然也能得到无重结果，但它剪掉的树枝较少，存在的无效计算较多，所以效率会差一些。
当然，关于排列去重，也有读者提出别的剪枝思路：
void backtrack(int[] nums, LinkedList<Integer> track) {
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
// 记录之前树枝上元素的值
// 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
int prevNum = -666;
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) {
continue;
}
if (nums[i] == prevNum) {
continue;
}
track.add(nums[i]);
used[i] = true;
// 记录这条树枝上的值
prevNum = nums[i];
backtrack(nums, track);
track.removeLast();
used[i] = false;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 回溯函数
// nums: 待选择的数组
// track: 记录当前选择的路径
void backtrack(vector<int>& nums, list<int>& track, vector<vector<int>>& res, vector<bool>& used) {
// 判断是否达到决策树底部，记录路径
if (track.size() == nums.size()) {
res.emplace_back(vector<int>(track.begin(), track.end()));
return;
}
// 记录之前树枝上元素的值
// 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
int prevNum = -666;
for (int i = 0; i < nums.size(); i++) {
// 排除不合法的选择
if (used[i]) {
continue;
}
if (nums[i] == prevNum) {
continue;
}
// 做选择
track.push_back(nums[i]);
used[i] = true;
// 记录这条树枝上的值
prevNum = nums[i];
// 进入下一层决策树
backtrack(nums, track, res, used);
// 撤销选择
track.pop_back();
used[i] = false;
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def backtrack(nums: List[int], track: LinkedList[int]):
# add type annotation on function params and reserve comments
# 初始化
# used 存储已经选择过的下标 i，避免重复选择
# res 用于存储结果
used = set()
res = []
# 递归回溯函数定义
def dfs():
# 到达叶子结点后，记录并返回
if len(track) == len(nums):
# 注意要加[:]
res.append(track[:])
return
# 记录之前树枝上元素的值
# 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
prev_num = -666
for i in range(len(nums)):
# 排除不合法的选择
if i in used or nums[i] == prev_num:
continue
# 做出选择
track.append(nums[i])
used.add(i)
# 记录这条树枝上的值
prev_num = nums[i]
# 进入下一层决策树
dfs()
# 取消选择
track.removeLast()
used.remove(i)
# 驱动函数
dfs()
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func backtrack(nums []int, track []int) {
if len(track) == len(nums) {
res = append(res, append([]int(nil), track...))
return
}
// 记录之前树枝上元素的值
// 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
var prevNum int = -666
for i := 0; i < len(nums); i++ {
// 排除不合法的选择
if used[i] {
continue
}
if nums[i] == prevNum {
continue
}
track = append(track, nums[i])
used[i] = true
// 记录这条树枝上的值
prevNum = nums[i]
backtrack(nums, track)
track = track[:len(track)-1]
used[i] = false
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* 记录之前树枝上元素的值
* 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
*/
var prevNum = -666;
/**
* 回溯函数
*
* @param {number[]} nums - 数组
* @param {LinkedList} track - 记录数组中已经选择的元素
*/
var backtrack = function (nums, track) {
// 如果track长度等于nums长度，说明track记录的已经是nums的所有元素了，就把track加入结果集
if (track.length === nums.length) {
res.push([...track]);
return;
}
for (let i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) {
continue;
}
if (nums[i] === prevNum) {
continue;
}
track.push(nums[i]);
used[i] = true;
// 记录这条树枝上的值
prevNum = nums[i];
backtrack(nums, track);
track.pop();
used[i] = false;
}
};
这个思路也是对的，设想一个节点出现了相同的树枝：
如果不作处理，这些相同树枝下面的子树也会长得一模一样，所以会出现重复的排列。
因为排序之后所有相等的元素都挨在一起，所以只要用 prevNum 记录前一条树枝的值，就可以避免遍历值相同的树枝，从而避免产生相同的子树，最终避免出现重复的排列。
好了，这样包含重复输入的排列问题也解决了。
子集/组合（元素无重可复选）
终于到了最后一种类型了：输入数组无重复元素，但每个元素可以被无限次使用。
直接看力扣第 39 题「 组合总和」：
给你一个无重复元素的整数数组 candidates 和一个目标和 target，找出 candidates 中可以使数字和为目标数 target 的所有组合。candidates 中的每个数字可以无限制重复被选取。
函数签名如下：
List<List<Integer>> combinationSum(int[] candidates, int target)
比如输入 candidates = [1,2,3], target = 3，算法应该返回：
[ [1,1,1],[1,2],[3] ]
这道题说是组合问题，实际上也是子集问题：candidates 的哪些子集的和为 target？
想解决这种类型的问题，也得回到回溯树上，我们不妨先思考思考，标准的子集/组合问题是如何保证不重复使用元素的？
答案在于 backtrack 递归时输入的参数 start：
// 无重组合的回溯算法框架
void backtrack(int[] nums, int start) {
for (int i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i + 1);
// ...
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 无重组合的回溯算法框架
void backtrack(vector<int>& nums, int start) {
for (int i = start; i < nums.size(); i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i + 1);
// ...
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 无重组合的回溯算法框架
def backtrack(nums: List[int], start: int) -> None:
for i in range(start, len(nums)):
# ...
# 递归遍历下一层回溯树，注意参数
backtrack(nums, i + 1)
# ...
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 无重组合的回溯算法框架
func backtrack(nums []int, start int) {
for i := start; i < len(nums); i++ {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i + 1)
// ...
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var backtrack = function(nums, start) {
for (var 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);
// ...
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 可重组合的回溯算法框架
void backtrack(vector<int>& nums, int start) {
for (int i = start; i < nums.size(); i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i);
// ...
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 可重组合的回溯算法框架
def backtrack(nums: List[int], start: int):
for i in range(start, len(nums)):
# ...
# 递归遍历下一层回溯树，注意参数
backtrack(nums, i)
# ...
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 可重组合的回溯算法框架
func backtrack(nums []int, start int) {
for i := start; i < len(nums); i++ {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i)
// ...
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var backtrack = function(nums, start) {
for (var i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树，注意参数
backtrack(nums, i);
// ...
}
};
这相当于给之前的回溯树添加了一条树枝，在遍历这棵树的过程中，一个元素可以被无限次使用：
当然，这样这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的 base case 以结束算法，即路径和大于 target 时就没必要再遍历下去了。
这道题的解法代码如下：
class Solution {
List<List<Integer>> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Integer> track = new LinkedList<>();
// 记录 track 中的路径和
int trackSum = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates.length == 0) {
return res;
}
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(int[] nums, int start, int target) {
// base case，找到目标和，记录结果
if (trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
// base case，超过目标和，停止向下遍历
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.length; i++) {
// 选择 nums[i]
trackSum += nums[i];
track.add(nums[i]);
// 递归遍历下一层回溯树
// 同一元素可重复使用，注意参数
backtrack(nums, i, target);
// 撤销选择 nums[i]
trackSum -= nums[i];
track.removeLast();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
public:
vector<vector<int>> res;
// 记录回溯的路径
deque<int> track;
// 记录 track 中的路径和
int trackSum = 0;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtrack(candidates, 0, target);
return res;
}
// 回溯算法主函数
void backtrack(vector<int>& nums, int start, int target) {
// base case，找到目标和，记录结果
if (trackSum == target) {
res.push_back(vector<int>(track.begin(), track.end()));
return;
}
// base case，超过目标和，停止向下遍历
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
// 选择 nums[i]
trackSum += nums[i];
track.push_back(nums[i]);
// 递归遍历下一层回溯树
// 同一元素可重复使用，注意参数
backtrack(nums, i, target);
// 撤销选择 nums[i]
trackSum -= nums[i];
track.pop_back();
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
def __init__(self):
self.res = []
# 记录回溯的路径
self.track = []
# 记录 track 中的路径和
self.trackSum = 0
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if len(candidates) == 0:
return self.res
self.backtrack(candidates, 0, target)
return self.res
# 回溯算法主函数
def backtrack(self, nums: List[int], start: int, target: int) -> None:
# base case，找到目标和，记录结果
if self.trackSum == target:
self.res.append(list(self.track))
return None
# base case，超过目标和，停止向下遍历
if self.trackSum > target:
return None
# 回溯算法标准框架
for i in range(start, len(nums)):
# 选择 nums[i]
self.trackSum += nums[i]
self.track.append(nums[i])
# 递归遍历下一层回溯树
# 同一元素可重复使用，注意参数
self.backtrack(nums, i, target)
# 撤销选择 nums[i]
self.trackSum -= nums[i]
self.track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func combinationSum(candidates []int, target int) [][]int {
res := make([][]int, 0) // 保存结果
track := make([]int, 0) // 保存回溯过程中的路径
backtrack(candidates, 0, target, track, 0, &res)
return res
}
// 回溯算法主函数
func backtrack(nums []int, start int, target int, track []int, trackSum int, res *[][]int) {
// base case, 找到目标和，记录结果
if trackSum == target {
*res = append(*res, append([]int{}, track...))
return
}
// base case，超过目标和，停止向下遍历
if trackSum > target {
return
}
// 回溯算法标准框架
for i := start; i < len(nums); i++ {
trackSum += nums[i]
track = append(track, nums[i])
backtrack(nums, i, target, track, trackSum, res)
trackSum -= nums[i]
track = track[:len(track)-1]
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
// 记录结果
var res = [];
// 记录回溯的路径
var track = [];
// 记录 track 中的路径和
var trackSum = 0;
// 回溯算法主函数
function backtrack(nums, start, target) {
// base case，找到目标和，记录结果
if (trackSum === target) {
res.push([...track]);
return;
}
// base case，超过目标和，停止向下遍历
if (trackSum > target) {
return;
}
// 回溯算法标准框架
for (var i = start; i < nums.length; i++) {
// 选择 nums[i]
trackSum += nums[i];
track.push(nums[i]);
// 递归遍历下一层回溯树
// 同一元素可重复使用，注意参数
backtrack(nums, i, target);
// 撤销选择 nums[i]
trackSum -= nums[i];
track.pop();
}
}
if (candidates.length === 0) {
return res;
}
backtrack(candidates, 0, target);
return res;
};
🎃 代码可视化动画 🎃
排列（元素无重可复选）
力扣上没有类似的题目，我们不妨先想一下，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 数组的剪枝逻辑就行了。
那这个问题就简单了，代码如下：
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();
}
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
class Solution {
private:
vector<vector<int>> res;
deque<int> track;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtrack(nums, used);
return res;
}
void backtrack(vector<int>& nums, vector<bool>& used) {
// base case，到达叶子节点
if (track.size() == nums.size()) {
// 收集叶子节点上的值
res.push_back(vector(track.begin(), track.end()));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.size(); i++) {
// 排除不合法选择
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
// 做选择
track.push_back(nums[i]);
used[i] = true;
// 进入下一层回溯树
backtrack(nums, used);
// 取消选择
track.pop_back();
used[i] = false;
}
}
};
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
class Solution:
def __init__(self):
self.res = []
self.track = []
def permuteRepeat(self, nums: List[int]) -> List[List[int]]:
self.backtrack(nums)
return self.res
# 回溯算法核心函数
def backtrack(self, nums: List[int]) -> None:
# base case，到达叶子节点
if len(self.track) == len(nums):
# 收集叶子节点上的值
self.res.append(self.track[:])
return
# 回溯算法标准框架
for i in range(len(nums)):
# 做选择
self.track.append(nums[i])
# 进入下一层回溯树
self.backtrack(nums)
# 取消选择
self.track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func permuteRepeat(nums []int) [][]int {
var res [][]int
track := []int{}
// 回溯核心函数
var backtrack func(nums []int)
backtrack = func(nums []int) {
// 如果选择的路径等于原数列长度，就收录这个排列
if len(track) == len(nums) {
res = append(res, append([]int(nil), track...))
return
}
for i := 0; i < len(nums); i++ {
// 如果路径中已经包含了当前选择，就跳过
if contains(track, nums[i]) {
continue
}
// 做选择
track = append(track, nums[i])
// 进入下一层回溯树
backtrack(nums)
// 取消选择
track = track[:len(track)-1]
}
}
backtrack(nums)
return res
}
// 判断一个切片中是否包含某个元素的函数
func contains(track []int, x int) bool {
for _, num := range track {
if num == x {
return true
}
}
return false
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteRepeat = function(nums) {
// 创建结果集和回溯路径
let res = [];
let track = [];
// 回溯算法核心函数
const backtrack = function(nums) {
// base case，到达叶子节点
if (track.length === nums.length) {
// 收集叶子节点上的值
res.push([...track]);
return;
}
// 回溯算法标准框架
for (let i = 0; i < nums.length; i++) {
// 做选择
track.push(nums[i]);
// 进入下一层回溯树
backtrack(nums);
// 取消选择
track.pop();
}
}
// 从第一层开始回溯
backtrack(nums);
return res;
};
至此，排列/组合/子集问题的九种变化就都讲完了。
最后总结
来回顾一下排列/组合/子集问题的三种形式在代码上的区别。
由于子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。
形式一、元素无重不可复选，即 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;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void backtrack(vector<int>& nums, int start) {
// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
// 做选择
track.push_back(nums[i]);
// 注意参数
backtrack(nums, i + 1);
// 撤销选择
track.pop_back();
}
}
void backtrack(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
// 剪枝逻辑
if (used[i]) {
continue;
}
// 做选择
used[i] = true;
track.push_back(nums[i]);
backtrack(nums);
// 撤销选择
track.pop_back();
used[i] = false;
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def backtrack(nums: List[int], start: int):
# 回溯算法标准框架
for i in range(start, len(nums)):
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i + 1)
# 撤销选择
track.pop()
def backtrack(nums: List[int]):
for i in range(len(nums)):
# 剪枝逻辑
if used[i]:
continue
# 做选择
used[i] = True
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
used[i] = False
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 组合/子集问题回溯算法框架
func backtrack(nums []int, start int) {
// 回溯算法标准框架
for i := start; i < len(nums); i++ {
// 做选择
track = append(track, nums[i])
// 注意参数
backtrack(nums, i+1)
// 撤销选择
track = track[:len(track)-1]
}
}
// 排列问题回溯算法框架
func backtrack(nums []int) {
for i := 0; i < len(nums); i++ {
// 剪枝逻辑
if used[i] {
continue
}
// 做选择
used[i] = true
track = append(track, nums[i])
backtrack(nums)
// 撤销选择
track = track[:len(track)-1]
used[i] = false
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 组合/子集问题回溯算法框架
var backtrack = function(nums, start) {
// 回溯算法标准框架
for (var i = start; i < nums.length; i++) {
// 做选择
track.addLast(nums[i]);
// 注意参数
backtrack(nums, i + 1);
// 撤销选择
track.removeLast();
}
}
// 排列问题回溯算法框架
var backtrack = function(nums) {
for (var 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;
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
sort(nums.begin(), nums.end());
/* 组合/子集问题回溯算法框架 */
void backtrack(vector<int>& nums, int start) {
//回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
// 剪枝逻辑，跳过值相同的相邻树枝
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// 做选择
track.push_back(nums[i]);
// 注意参数
backtrack(nums, i + 1);
// 撤销选择
track.pop_back();
}
}
sort(nums.begin(), nums.end());
/* 排列问题回溯算法框架 */
void backtrack(vector<int>& nums, vector<bool>& used) {
for (int i = 0; i < nums.size(); i++) {
// 剪枝逻辑
if (used[i]) {
continue;
}
// 剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
// 做选择
used[i] = true;
track.push_back(nums[i]);
backtrack(nums, used);
// 撤销选择
track.pop_back();
used[i] = false;
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
nums.sort()
# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):
# 回溯算法标准框架
for i in range(start, len(nums)):
# 剪枝逻辑，跳过值相同的相邻树枝
if i > start and nums[i] == nums[i - 1]:
continue
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i + 1)
# 撤销选择
track.pop()
nums.sort()
# 排列问题回溯算法框架
def backtrack(nums: List[int]):
for i in range(len(nums)):
# 剪枝逻辑
if used[i]:
continue
# 剪枝逻辑，固定相同的元素在排列中的相对位置
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
# 做选择
used[i] = True
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
used[i] = False
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
import "sort"
func backtrack(nums []int, start int) {
// 回溯算法标准框架
for i := start; i < len(nums); i++ {
// 剪枝逻辑，跳过值相同的相邻树枝
if i > start && nums[i] == nums[i-1] {
continue
}
// 做选择
track = append(track, nums[i])
// 注意参数
backtrack(nums, i+1)
// 撤销选择
track = track[:len(track)-1]
}
}
func combinations(nums []int) {
// 预处理排序
sort.Ints(nums)
backtrack(nums, 0)
}
func backtrack(nums []int) {
for i := 0; i < len(nums); i++ {
// 剪枝逻辑
if used[i] {
continue
}
// 剪枝逻辑，固定相同的元素在排列中的相对位置
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
// 做选择
used[i] = true
track = append(track, nums[i])
backtrack(nums)
// 撤销选择
track = track[:len(track)-1]
used[i] = false
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var backtrack = (nums, start, track, used) => {
nums = nums.sort();
if (!used) {
used = Array(nums.length).fill(false);
}
if (!track) {
track = [];
}
if (track.length === nums.length) {
// 结果处理
return;
}
for (let i = start; i < nums.length; i++) {
// 剪枝逻辑，跳过值相同的相邻树枝
if (i > start && nums[i] === nums[i - 1]) {
continue;
}
// 做选择
track.push(nums[i]);
used[i] = true;
// 注意参数
backtrack(nums, i + 1, track, used);
// 撤销选择
track.pop();
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();
}
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/* 组合/子集问题回溯算法框架 */
void backtrack(vector<int>& nums, int start, vector<int>& track) {
// 回溯算法标准框架
for (int i = start; i < nums.size(); i++) {
// 做选择
track.push_back(nums[i]);
// 注意参数
backtrack(nums, i+1, track);
// 撤销选择
track.pop_back();
}
}
/* 排列问题回溯算法框架 */
void backtrack(vector<int>& nums, vector<int>& track) {
if (track.size() == nums.size()) {
// 输出结果
// ...
return;
}
for (int i = 0; i < nums.size(); i++) {
// 排除不合法的选择
if (find(track.begin(), track.end(), nums[i]) != track.end()) {
continue;
}
// 做选择
track.push_back(nums[i]);
backtrack(nums, track);
// 撤销选择
track.pop_back();
}
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):
# 回溯算法标准框架
for i in range(start, len(nums)):
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i)
# 撤销选择
track.pop()
# 排列问题回溯算法框架
def backtrack(nums: List[int]):
for i in range(len(nums)):
# 做选择
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func backtrack(nums []int, start int) {
// 回溯算法标准框架
for i := start; i < len(nums); i++ {
// 做选择
track = append(track, nums[i])
// 注意参数
backtrack(nums, i)
// 撤销选择
track = track[:len(track)-1]
}
}
func backtrack(nums []int) {
for i := 0; i < len(nums); i++ {
// 做选择
track = append(track, nums[i])
backtrack(nums)
// 撤销选择
track = track[:len(track)-1]
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var backtrack = function(nums, start) {
// 回溯算法标准框架
for (var i = start; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
// 注意参数
backtrack(nums, i);
// 撤销选择
track.pop();
}
};
var backtrack = function(nums) {
// 排列问题回溯算法框架
for (var i = 0; i < nums.length; i++) {
// 做选择
track.add(nums[i]);
backtrack(nums);
// 撤销选择
track.pop();
}
};
只要从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决，这也是为什么我在 学习算法和数据结构的框架思维 和 手把手刷二叉树（纲领篇） 中强调树类型题目重要性的原因。
如果你能够看到这里，真得给你鼓掌，相信你以后遇到各种乱七八糟的算法题，也能一眼看透它们的本质，以不变应万变。另外，考虑到篇幅，本文并没有对这些算法进行复杂度的分析，你可以使用我在 算法时空复杂度分析实用指南 讲到的复杂度分析方法尝试自己分析它们的复杂度。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释