读完本文,你不仅学会了算法套路,还能够顺便去 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,欢送点赞!