Day 29 回溯算法

如果直接像下面这样写的话，会出错，出错的案例类似：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9nrEEc2S-1688623883770)(LC491-递增子序列+LC.assets/image-20230703201315163.png)]

class Solution {vector<vector<int>> rst;vector<int> path;void backtracking(const vector<int> &nums, int idx){if (path.size() > 1){rst.push_back(path);}for (int i = idx; i < nums.size(); i++){if (i > idx && nums[i] == nums[i - 1]) // 不能使用这一去重逻辑{continue;}if (path.empty() || path.back() <= nums[i]){path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}}public:vector<vector<int>> findSubsequences(vector<int>& nums) {rst.clear();path.clear();backtracking(nums, 0);return rst;}
};

本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑！

同一父节点下的同层上使用过的元素就不能再使用了

正确的写法如下：

class Solution {vector<vector<int>> rst;vector<int> path;void backtracking(const vector<int> &nums, int idx){if (path.size() > 1){rst.push_back(path);}int used[201] = {0};for (int i = idx; i < nums.size(); i++){if ((!path.empty() && path.back() > nums[i]) || used[nums[i] + 100]){continue;}used[nums[i] + 100] = 1;path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}public:vector<vector<int>> findSubsequences(vector<int>& nums) {rst.clear();path.clear();backtracking(nums, 0);return rst;}
};

需要有一个used数组来记录已经被使用过的元素索引

class Solution {vector<vector<int>> rst;vector<int> path;void backtracking(const vector<int> &nums, vector<bool> &used) {if (path.size() == nums.size()){rst.push_back(path);return;}for (int i = 0; i < nums.size(); ++i){if (used[i]) continue;used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}public:vector<vector<int>> permute(vector<int>& nums) {rst.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return rst;}
};

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

class Solution {vector<vector<int>> rst;vector<int> path;void backtracking(const vector<int> &nums, vector<bool> &used){if (path.size() == nums.size()){rst.push_back(path);return;}for (int i = 0; i < nums.size(); ++i){if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}if (!used[i]){used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}}public:vector<vector<int>> permuteUnique(vector<int>& nums) {rst.clear();path.clear();sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return rst;}
};