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

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.