LeetCode 491 递增子序列 - 回溯解法
https://leetcode.cn/problems/non-decreasing-subsequences/description/
思路
和求子集问题类似，函数语义为：从index 到最后中选择一个数加入到path中。
for(int i = index;i<max;i++){
if(loc[i]合法){
加入
addPath(i+1)
pop
}
}
但是， 会有重复的问题， [4,6,7,7]
所以还要去重，这里的重复是 你和兄弟们的重复
两个 467 重复了，在 for 循环遍历到 第一个7 后，第二个 7 就不该遍历， 针对这种可以借鉴之前[组合总和2](LeetCode 40 组合总和 II - 回溯解法.md) 设置 last 来存储上一次的值。
数据范围<100 设置为101
int last = 101
for(int i = index;i<max;i++){
if(loc[i]==last) continue;
if(loc[i]合法){
加入
addPath(i+1)
pop
}
}
提交后发现没通过，[4,6,7,7,4,4]
这里 last=7 不起作用， 因此要设置 used 数组，每回加入的时候要查一下。
use[101] 全是101
for(int i = index;i<max;i++){
if(used(loc[i])) continue;
if(loc[i]合法){
加入
addPath(i+1)
pop
}
}
代码
class Solution {
public:
vector<int> loc_nums;
vector<int> path;
vector<vector<int>> result;
bool is_used(vector<int> use, int value) {
for (int i = 0; i < use.size(); i++) {
if (use[i] == value) {
return true;
}
}
return false;
}
void add_path(int index) {
if (path.size() >= 2) {
result.push_back(path);
}
vector<int> use(loc_nums.size()-index,101);
for (int i = index; i < loc_nums.size(); i++) {
if (is_used(use, loc_nums[i]))
continue;
use.push_back(loc_nums[i]);
if (path.size() == 0 || loc_nums[i] >= path.back()) {
path.push_back(loc_nums[i]);
add_path(i + 1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
loc_nums = nums;
add_path(0);
return result;
}
};