491.Non-decreasing Subsequences
===

###### tags: `Medium`,`Array`,`Hash Table`,`Backtracking`,`Bit Manipulation`

[491. Non-decreasing Subsequences](https://leetcode.com/problems/non-decreasing-subsequences/)

### 題目描述

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]]

**Constraints**:

* 1 <= `nums.length` <= 15
* -100 <= `nums[i]` <= 100

### 解答
#### C++

class Solution {
public:
    void dfs(vector<int>& nums, set<vector<int>>& ans, vector<int>& path, int i = 0) {
        if (i >= nums.size()) {
            if (path.size() >= 2) ans.insert(path);
            return;
        }
        if (path.size() == 0 || nums[i] >= path.back()) {
            path.push_back(nums[i]);
            dfs(nums, ans, path, i+1);
            path.pop_back();
        }
        dfs(nums, ans, path, i+1);
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> ans;
        vector<int> path;
        dfs(nums, ans, path);
        return vector(ans.begin(), ans.end());
    }
};

> Backtracking走一遍就好
> [name=Yen-Chi Chen][time=Fri, Jan 20, 2023]

#### Python

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        ans = set()

        def BT(path = [], i = 0):
            if i >= len(nums):
                if len(path) >= 2: ans.add(tuple(path))
                return
            if not path or nums[i] >= path[-1]:
                BT(path + [nums[i]], i+1)
            BT(path, i+1)
        
        BT()
        return ans

> [name=Yen-Chi Chen][time=Fri, Jan 20, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)