摘要
在回溯法的树形结构的同一层中去重，可以使用
set进行去重，这样无需重新排列待选元素。全排列问题使用
used数组来进行树枝去重（即在同一条路径上不使用相同的元素）更方便。
LeetCode491 递增子序列
这题的
nums代表的是序列，要求的也是递增子序列。nums中的元素的顺序是不能改变的，不能对nums进行排序后来对连续分布的值相同的元素进行去重。只能通过在每层中引入一个set来记录当前层已经从哪些元素开始过。以
nums = [1, 2, 3, 1, 1]为例，其递增子序列的树形结构如下图
- 树层去重，其在回溯法的树形结构的同一层中，第一次选择值为
x的元素时再往下的搜索结果，已经包含了在本层中再次选择值为x的元素的结果。也就是说，在同一层中，对于每个值x，只需要保留第一次遇到值为x的元素的搜索结果，再次遇到值为x的元素不需要再向下搜索。就可以完成树层去重。
完整的题解代码如下
class Solution {
public:
void backtracking(vector<int>& nums, vector<vector<int>>& res,
vector<int>& cur, int start)
{
if (cur.size() >= 2) res.push_back(cur);
if (start >= nums.size()) {
return;
}
unordered_set<int> fused;
for (int i = start; i < nums.size(); i++) {
if (i - start && nums[i - 1] == nums[i]) continue;
if (i - start && fused.count(nums[i])) continue;
if (cur.empty() || nums[i] >= cur.back()) {
cur.push_back(nums[i]);
fused.insert(nums[i]);
backtracking(nums, res, cur, i + 1);
cur.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
map<int, bool> fused;
backtracking(nums, res, cur, 0);
return res;
}
};
- 包含树层去重的回溯法的递归函数的结构
void backtracking(vector<int>& nums, vector<vector<int>>& res,
vector<int>& cur, int start)
{
if (/* 递归终止条件 */) {
return;
}
/* 本层的局部变量 */
for (int i = start; i < nums.size(); i++) {
/* 向下搜索的逻辑 */
}
}
LeetCode46 全排列
- 本题算是排列问题的入门，所以先复习一下组合和排列的概念，以便对比
| 组合 | 排列 |
|---|---|
| 不强调元素的顺序 | 强调元素的顺序 |
| 相当于数学中的“集合”（但元素的值可以相同） | 相当于数学中的“数列” |
而组合问题和排列问题都要进行“树枝去重”，即在树形结构的同一条路径上，不能重复使用同一个元素。组合问题和排列问题在“树枝去重”的实现上是不同的。
| 组合 | 排列 |
|---|---|
| 下一层的可选元素的起始位置向右移一位 | 下一层的可选元素的起始位置仍然从0开始 |
可以通过used数组实现 |
一般只能通过used数组实现 |
也可以通过右移可选元素start的起始位置实现 |
因为排列需要改变待选元素的顺序，不能保证start之后的元素都未被选取过 |
- 以
[1,2,3]为例
- 在“全排列”的问题中，下一层元素也是要从第一个元素开始的，而不是从当前节点的下一个元素开始。所以，就需要一个数组来保存哪个元素使用过，哪个元素没有使用过。即
used数组。
完整的题解代码如下
class Solution {
public:
void backtracking(vector<int>& nums, vector<vector<int>>& res,
vector<int>& cur, vector<bool>& used)
{
if (cur.size() == nums.size()) {
res.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
cur.push_back(nums[i]);
used[i] = true;
backtracking(nums, res, cur, used);
used[i] = false;
cur.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
vector<bool> used(nums.size());
backtracking(nums, res, cur, used);
return res;
}
};
附组合问题的题解代码，以便对比
class Solution {
public:
void backtracking(vector<vector<int>>& res, int& n, int& k,
vector<int>& cur, int start)
{
if (cur.size() == k) {
res.push_back(cur);
return;
}
for (int i = start; i <= n - (k - cur.size()) + 1; i++) {
cur.push_back(i);
backtracking(res, n, k, cur, i + 1);
cur.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> cur;
backtracking(res, n, k, cur, 1);
return res;
}
};
LeetCode47 全排列II
- 以
[1,1,2]为例，其树形结构如下
- 本题需要做“树层去重”：在同一层中，排除第一次选到值为
x的元素之后再次选到值为x的元素的情况。 - 本题也需要做"树枝去重"：在同一条路径上，不能选取相同的元素。
用used数组来标记哪些元素使用过可以简单地实现树枝去重。
对于树层去重，一般有以下两种方式
- 一是用
set进行树层去重，这适用于不可以改变待选元素序列的情况，对于可以对待选元素重新排序的情况，将待选元素重新排列后进行去重效率更高。 - 二是将待选元素进行重新排序，让值相同的元素连续分布，便于判断是否是第一次取到某个值的元素，这种实现方式比使用
set效率高，但会改变待选元素本来的顺序。
使用unordered_set的题解代码
class Solution {
public:
void backtracking(vector<int>& nums, vector<vector<int>>& res,
vector<int>& cur, vector<bool>& used)
{
if (cur.size() == nums.size()) {
res.push_back(cur);
return;
}
unordered_set<int> level;
for (int i = 0; i < nums.size(); i++) {
if (used[i] || level.count(nums[i])) continue;
cur.push_back(nums[i]);
used[i] = true;
level.insert(nums[i]);
backtracking(nums, res, cur, used);
used[i] = false;
cur.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
vector<bool> used(nums.size());
backtracking(nums, res, cur, used);
return res;
}
};
重新排序待选元素的题解代码如下
class Solution {
public:
void backtracking(vector<int>& nums, vector<vector<int>>& res,
vector<int>& cur, vector<bool>& used)
{
if (cur.size() == nums.size()) {
res.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (i && nums[i - 1] == nums[i] && !used[i - 1]) continue;
if (used[i]) continue;
cur.push_back(nums[i]);
used[i] = true;
backtracking(nums, res, cur, used);
used[i] = false;
cur.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
vector<bool> used(nums.size());
sort(nums.begin(), nums.end());
backtracking(nums, res, cur, used);
return res;
}
};
image.png
