# C++ O(2^N) dfs and using vector

• ``````class Solution {
public:
vector<vector<int>> ret;
vector<int> prev;
vector<int> subSeq;
void dfs(vector<int>& nums, int idx)
{
if(subSeq.size() > 1)ret.push_back(subSeq);
for (int i = idx; i < nums.size(); i++)
{
//1. The first condition is about duplication.
//if prev[i] is in the avail range[idx, nums.size()), i should be ignored
//2. other conditions are about increasement.
if ((idx > prev[i]) && (subSeq.size() == 0 || subSeq[subSeq.size() - 1] <= nums[i]))
{
subSeq.push_back(nums[i]);
dfs(nums, i + 1);
subSeq.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
int subSeq = 0;
prev = vector<int>(nums.size(), -1);
vector<int> last(201,-1);
// previous position of what has same number with num[i] is prev[i]
for (int i = 0; i < nums.size(); i++)last[nums[i] + 100] = -1;
for (int i = 0 ; i < nums.size() ; i++)
{
prev[i] = last[nums[i] + 100];
last[nums[i] + 100] = i;
}
dfs(nums,  0);
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.