dfs搜索所有的非递减序列
C++ 代码
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(nums, 0);
return res;
}
void dfs(vector<int>& nums, int start) {
// 任何子搜索空间满足条件的中间结果都需要记录下来
if(path.size() >= 2) res.push_back(path);
if(start == nums.size()) return;
// 记录该所搜分支上面曾经出现的数字,比如 第二个搜索的数字是3
// 那后面就不用在第二个数字放3了,因为是重复的
unordered_set<int> dp;
// 规定搜索顺序,从左向右搜索
for(int i=start; i<nums.size(); ++i) {
int num = nums[i];
// 去重
if(dp.count(num))continue;
// 非递减序列
if(path.empty() || path.back() <= num) {
dp.insert(num);
path.push_back(num);
dfs(nums, i+1);
path.pop_back();
}
}
}
private:
vector<vector<int>> res;
vector<int> path;
};