目录
题目链接：491.递增子序列
思路
求递增子序列，其实也是求子集的一种，只是添加了限定条件。首先，子序列中元素的个数大于等于2，其次是保证递增，最后不能有重复的子序列。
元素个数可以比较path中元素个数来保证；递增可以通过对比当前要收集的元素与path中第一个元素对比来保证；最后一点，去重，之前做的题去重都是对数组进行了排序，但是这道题对顺序有要求，不能重排数组，所以使用set把遍历过的元素存进去，如果发现当前遍历的元素已经遍历过了，则不收集结果，继续循环。
代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startindex) {
// 保证子序列至少有两个元素
if (path.size() > 1)
result.push_back(path);
unordered_set<int> uset; // 存每层遍历过的元素，用来去重
for (int i = startindex; i < nums.size(); i++) {
// path非空，并且当前元素大于path中第一个元素
// 或者在uset中出现过当前元素
// 满足上述条件，则不进行结果收集
if (!path.empty() && nums[i] < path.back() ||
uset.find(nums[i]) != uset.end()) {
continue;
}
path.push_back(nums[i]); // 将当前元素存进path
uset.insert(nums[i]); // 存进uset
backtracking(nums, i + 1); // 递归
path.pop_back(); // 回溯
}
return;
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};题目链接：46.全排列
思路
排列与组合不同的是，排列中要包含所有元素，而且只要排列顺序不同，就是不同的排列结果。因此根据这两个特点来写回溯代码。
在结果收集上，是在叶子节点进行收集，当path元素个数等于nums元素个数时进行结果收集
因为排列中要包含所有元素，所以每一层遍历都要遍历整个数组，但是为了避免收集已经使用过的元素，使用bool型的used数组。每加入一个元素将其对应的used置1，如果当前元素已经加入到了path中，不收集当前元素，继续循环。
代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {
// 全排列要求每个结果包含数组中所有元素，只是排列顺序不同
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// 使用used数组来避免取到重复元素
if (used[i] == true) {
continue;
}
path.push_back(nums[i]); // 存进path
used[i] = true; // used置1
backtracking(nums, used); // 递归
path.pop_back(); // 回溯
used[i] = false; // used置0
}
return;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};题目链接：47.全排列 II
思路
与46.全排列不同的是数组中有重复元素，所以只需对上述代码进行更改，加入去重的操作即可。这里的去重与之前数组中有重复元素的组合类似，只进行树层去重，所以上述代码中的used数组有了第二个作用，树层去重。
对数组进行排序后，当前元素与上一个元素相等，并且上一个元素的used为false，这就说明，该进行树层去重了，当前元素所收集的结果，在遍历上一个元素时已经收集过了，所以跳过当前元素。
如果当前元素与上一个元素相等，但是上一个元素的used为true，这说明这两个元素不在同一树层，或者说当前元素所在树层比上一个元素深一层，所以可以进行结果收集，例如[2,1,1]这种情况。
代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used作用有两个
// 一是为了避免加入排列内元素重复
// 二是为了树层去重
// 去重,与之前的组合类似
// 当前元素与上一个元素相等，并且上一个元素还为加入path中
// 说明这是树枝的开始，直接舍弃
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
// 当前元素还未加入path中，所以可以进行节点处理
if (used[i] == false) {
path.push_back(nums[i]); // 节点处理
used[i] = true;
backtracking(nums, used); // 递归
path.pop_back(); // 回溯
used[i] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 对数组排序，用于去重
backtracking(nums, used);
return result;
}
};总结
①递增子序列也是组合问题的一种，只是加了一些限定条件，所以在原先回溯代码的模板上将限定条件加上即可
②排列问题，排列中包含所有元素，顺序不同即结果不同，最后结果不能有重复排列。由于结果要求包含所有元素，所以每次都要对整个数组进行遍历，为了防止有重复元素加入，使用bool 型的used数组记录使用过的元素
③数组中有重复元素时，去重思路与之前的组合问题类似，先对数组进行排序，然后利用used数组进行树层去重
④目前接触到的使用回溯算法的问题，大体上都是同一个思路，只是要将不同问题的限定条件体现在框架当中