共计 12324 个字符，预计需要花费 31 分钟才能阅读完成。
读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
78. 子集（中等）
90. 子集 II（中等）
77. 组合（中等）
39. 组合总和（中等）
40. 组合总和 II（中等）
216. 组合总和 III（中等）
46. 全排列（中等）
47. 全排列 II（中等）
———–
尽管这几个问题是高中就学过的，但如果想编写算法决这几类问题，还是十分考验计算机思维的，本文就讲讲编程解决这几个问题的外围思路，当前再有什么变体，你也能手到擒来，以不变应万变。
无论是排列、组合还是子集问题，简略说无非就是让你从序列 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)比方输出 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 的子集就是这一层节点的值：
PS：留神，本文之后所说「节点的值」都是指节点和根节点之间树枝上的元素，且将根节点认为是第 0 层。
那么再进一步，如果想计算所有子集，那只有遍历这棵多叉树，把所有节点的值收集起来不就行了？
间接看代码：
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();}
}看过前文 回溯算法外围框架 的读者应该很容易了解这段代码把，咱们应用 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)比方 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 层节点的值即可：
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();}
}这样，规范的子集问题也解决了。
排列（元素无重不可复选）
排列问题在前文 回溯算法外围框架 讲过，这里就简略过一下。
力扣第 46 题「全排列」就是规范的排列问题：
给定一个 不含反复数字 的数组 nums，返回其所有可能的 全排列。
函数签名如下：
List<List<Integer>> permute(int[] 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 数组标记曾经在门路上的元素防止反复抉择，而后收集所有叶子节点上的值，就是所有全排列的后果：
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;
}
}这样，全排列问题就解决了。
但如果题目不让你算全排列，而是让你算元素个数为 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);
// ...
}
}子集 / 组合（元素可重不可复选）
方才讲的规范子集问题输出的 nums 是没有反复元素的，但如果存在反复元素，怎么解决呢？
力扣第 90 题「子集 II」就是这样一个问题：
给你一个整数数组 nums，其中可能蕴含反复元素，请你返回该数组所有可能的子集。
函数签名如下：
List<List<Integer>> subsetsWithDup(int[] 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']
]所以咱们须要进行剪枝，如果一个节点有多条值雷同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：
体现在代码上，须要先进行排序，让雷同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
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();}
}这段代码和之前规范的子集问题的代码简直雷同，就是增加了排序和剪枝的逻辑。
至于为什么要这样剪枝，联合后面的图应该也很容易了解，这样带反复元素的子集问题也解决了。
咱们说了组合问题和子集问题是等价的，所以咱们间接看一道组合的题目吧，这是力扣第 40 题「组合总和 II」：
给你输出 candidates 和一个指标和 target，从 candidates 中找出中所有和为 target 的组合。
candidates 可能存在反复元素，且其中的每个数字最多只能应用一次。
说这是一个组合问题，其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。
所以这题怎么做呢？
比照子集问题的解法，只有额定用一个 trackSum 变量记录回溯门路上的元素和，而后将 base case 改一改即可解决这道题：
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([i]);
trackSum += nums[i];
// 递归遍历下一层回溯树
backtrack(nums, i + 1, target);
// 撤销抉择
track.removeLast();
trackSum -= nums[i];
}
}排列（元素可重不可复选）
排列问题的输出如果存在反复，比子集 / 组合问题略微简单一点，咱们看看力扣第 47 题「全排列 II」：
给你输出一个可蕴含反复数字的序列 nums，请你写一个算法，返回所有可能的全排列，函数签名如下：
List<List<Integer>> permuteUnique(int[] nums)比方输出 nums = [1,2,2]，函数返回：
[[1,2,2],[2,1,2],[2,2,1] ]先看解法代码：
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, track);
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;
}
}你比照一下之前的规范全排列解法代码，这段解法代码只有两处不同：
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' 曾经被应用的状况下才会被抉择，这就保障了雷同元素在排列中的绝对地位保障固定。
好了，这样蕴含反复输出的排列问题也解决了。
子集 / 组合（元素无重可复选）
终于到了最初一种类型了：输出数组无反复元素，但每个元素能够被有限次应用。
间接看力扣第 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 递归时输出的参数：
// 回溯算法规范框架
for (int i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树，留神参数
backtrack(nums, i + 1, target);
// ...
}这个 i 从 start 开始，那么下一层回溯树就是从 start + 1 开始，从而保障 nums[start] 这个元素不会被重复使用：
那么反过来，如果我想让每个元素被重复使用，我只有把 i + 1 改成 i 即可：
// 回溯算法规范框架
for (int i = start; i < nums.length; i++) {
// ...
// 递归遍历下一层回溯树
backtrack(nums, i, target);
// ...
}这相当于给之前的回溯树增加了一条树枝，在遍历这棵树的过程中，一个元素能够被有限次应用：
当然，这样这棵回溯树会永远成长上来，所以咱们的递归函数须要设置适合的 base case 以完结算法，即门路和大于 target 时就没必要再遍历上来了。
这道题的解法代码如下：
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();}
}排列（元素无重可复选）
力扣上没有相似的题目，咱们无妨先想一下，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 数组的剪枝逻辑就行了。
那这个问题就简略了，代码如下：
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();}
}至此，排列 / 组合 / 子集问题的九种变动就都讲完了。
最初总结
来回顾一下排列 / 组合 / 子集问题的三种模式在代码上的区别。
因为子集问题和组合问题实质上是一样的，无非就是 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;
}
}模式二、元素可重不可复选，即 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();}
}只有从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决，这也是为什么我在 学习算法和数据结构的框架思维 和 手把手刷二叉树（纲领篇）中强调树类型题目重要性的起因。
如果你可能看到这里，真得给你鼓掌，置信你当前遇到各种乌七八糟的算法题，也能一眼看透它们的实质，以不变应万变。
_____________
点击我的头像 查看更多优质算法文章，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 100k star，欢送点赞！