# DSA - Non decreasing Subsequences - C++,Dynamic Programming

## Non decreasing Subsequences

Hey, so today we are going to solve Leetcode - **Non decreasing Subsequences**

**Problem Link-** https://leetcode.com/problems/non-decreasing-subsequences

```
class Solution {
public:
void solve(vector<vector<int>> ans, vector<int> seq, vector<int>& nums, int i) {
if(seq.size() > 1) {
ans.emplace_back(seq);
}
unordered_set<int> used;
for(int i =0; i<nums.size(); i++) {
if(used.count(nums[i])) continue;
if(seq.empty() || nums[i] > seq.back() ) {
used.insert(nums[i]);
seq.push_back(nums[i]);
solve(ans, seq, nums, i+1);
seq.pop_back()
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> seq;
solve(ans, seq, nums, 0);
return ans;
}
}
```

The given code implements a backtracking algorithm to find all increasing subsequences of a given input vector `nums`

. The algorithm recursively builds increasing subsequences starting at each index of `nums`

, and avoids adding duplicate elements in the same subsequence by using an unordered set. If a subsequence has a length greater than 1, it is added to the final result vector `ans`

.

Let's take an example to understand the implementation step by step. Consider the input vector `nums`

as [4,6,7,7]. The algorithm begins by initializing `ans`

and `seq`

as empty vectors.

In the first call to the `solve`

function, `seq`

is empty and the loop iterates over all elements of `nums`

. At i=0, 4 is pushed onto `seq`

and the function is recursively called again with `i=1`

. At i=1, 6 is pushed onto `seq`

and the function is called recursively again with `i=2`

. At i=2, 7 is pushed onto `seq`

and the function is called recursively again with `i=3`

. At i=3, 7 is already in the unordered set, so the loop continues without pushing 7 onto `seq`

. At this point, `seq`

has the value [4,6,7]. Since this subsequence has length greater than 1, it is added to `ans`

.

Next, the algorithm backtracks to the previous call with `i=2`

, where `seq`

had the value [4,6]. The loop continues to check the remaining element 7, which is not added to `seq`

since it is already in the unordered set. The loop then terminates and the function returns to the previous call with `i=1`

, where `seq`

had the value [4]. The loop continues and checks the remaining elements 6,7,7 in `nums`

. 6 is added to `seq`

and a new subsequence [4,6] is added to `ans`

. The algorithm continues in this way, exploring all possible increasing subsequences of `nums`

.

Finally, the function returns the vector `ans`

containing all increasing subsequences of `nums`

.