题目链接:491. 递增子序列
方法:回溯 + 剪枝
解题思路
- 回溯:在每一个位置的时候判断当前元素是否可选,即是否大于等于前一个元素,满足条件时选取;
- 剪枝:由于本题目要求不能出现重复的子序列,也就是在回溯的每一层中选择的元素不能相同,因此可以在每一层设置一个平衡树,检测当前元素是否已经在该层的平衡树中,若在则不加入,否则加入。
代码
class Solution {
private:
int n;
vector<vector<int>> ans;
vector<int> cur;
public:
void dfs(int i, vector<int>& nums){
if (cur.size() >= 2) {
ans.push_back(cur);
}
unordered_set<int> s;
for (int j = i + 1; j < n; j ++ ) {
if (s.count(nums[j])) continue;
if (i == -1 || nums[j] >= nums[i]) {
cur.push_back(nums[j]);
s.insert(nums[j]);
dfs(j, nums);
cur.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
n = nums.size();
dfs(-1, nums);
return ans;
}
};
复杂度分析
时间复杂度:\(O(n * 2^n)\);
空间复杂度:\(O(n)\)。