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