491. Non-decreasing Subsequences ---M !!!!

 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

A ：

一开始，想每次插入，记录之前的最后一个值的找到的个数。 然而还是不够，需要记录更多。

第二个思路， 用set来记录已经有过了的。但是需要把 vector<int> 转成string 来做hash。 就是有点儿麻烦，转来转去的。

 in C++, you can use set<vector<int>> ans; — it works correctly as long as you include the necessary headers and use std::vector elements that are comparable.

unordered_set<vector<int>> ans; will NOT work by default in C++ ❌ — because std::unordered_set requires a hash function for its key type, and std::vector<int> does not have a built-in std::hash.

因此如果是python，就简单太多了

class Solution:

def findSubsequences(self, nums: List[int]) -> List[List[int]]:

ans = set()

def sol(path, remaining):

if len(path) > 1 and path == sorted(path):

ans.add(tuple(path))

for i in range(len(remaining)):

sol(path + [remaining[i]], remaining[i+1:])

sol([], nums)

return sorted(ans)

第三个思路： 核心困难点就在于重复的值。 首先找到所有不重复的。再插入把重复的值val，比如有n次，就替换为 1，2，3.。。n次   但是这个也会有问题。 算了，，看答案吧。 TNND

class Solution {

public:

vector<vector<int>> findSubsequences(vector<int>& nums) {

set<vector<int>> S;

vector<int> pre;

helper(nums, 0, pre, S);

return vector(S.begin(), S.end());

}

private:

void helper(vector<int>& nums, int start, vector<int>& pre, set<vector<int>>& S ){

int n = nums.size();

if(start >= n){

if(pre.size() >= 2){

S.insert(pre);

}

return;

}

// do not use

helper(nums, start+1, pre, S);

// consider to use this value

if(pre.size() == 0 || pre.back()<= nums[start]){

pre.push_back(nums[start]);

helper(nums, start+1, pre, S);

pre.pop_back();

}

}

};

Learned:

    unordered_set<vector<int>> S;

这样是不行的，因为 vector<int> 没有一个确定的hash函数。

thus we have to either define our own Hashable , 但是可以用set<vector<int>>