# LC 491. Non-decreasing Subsequences

### [Problem link](https://leetcode.com/problems/non-decreasing-subsequences/)

###### tags: `leedcode` `medium` `c++` `Backtracking`

Given an integer array <code>nums</code>, 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]]

**Constraints:**

- <code>1 <= nums.length <= 15</code>
- <code>-100 <= nums[i] <= 100</code>

## Solution 1
#### C++

class Solution {
public:
    vector<vector<int>> res;

    void backtracking(vector<int> &nums, vector<int> &path, int startIdx) {
        if (path.size() >= 2) {
            res.push_back(path);
        }

        unordered_set<int> uset;
        for (int i = startIdx; i < nums.size(); i++) {
            if (!path.empty() && path.back() > nums[i]) {
                continue;
            }
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums, path, i + 1);
            path.pop_back();
        }
    }

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

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n * $2^n$) | O(n) |

## Note
相比於[LC 90. Subsets II](https://hackmd.io/@Alone0506/HyGb-i7bR), 由於不能排序所以無法用nums[i - 1] == nums[i]這樣來判斷是否有取到同樣的數字, 所以額外需要一個set來記錄有沒有取過.