491 - Non-decreasing Subsequences

#medium

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

Example 1:
Input: nums = [4,6,7,7]
Output: [ [4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7] ]

Example 2:
Input: nums = [4,4,3,2,1]
Output: [ [4,4] ]

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking( vector<int> nums, int startIndex ) {
        if ( path.size() > 1 ) {
            result.push_back( path );
        }
        
        // 要記得去重，[4,7] 有可能出現兩個，因為7有兩個。
        // [樹枝上可以重複取(垂直)，但樹層上不能重複取(水平)]。
        // 樹層上不能取已經取過的數。
        unordered_set<int> uset;
        for ( int i = startIndex; i < nums.size(); i++ ) {
            if ( ( !path.empty() && path.back() > nums[i] ) || uset.find(nums[i]) != uset.end() ) continue;
            uset.insert(nums[i]);
            path.push_back( nums[i] );
            backtracking( nums, i + 1 );
            path.pop_back();

        }

    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking( nums, 0 );
        return result;    
    }
};