描述
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
提示：
1 <= nums.length <= 15
-100 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/non-decreasing-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
这道题目可以使用回溯算法来解决。在回溯算法中，我们需要维护一个路径（path），表示当前已经选了哪些数，以及一个选择列表（choices），表示当前还可以选择哪些数。在每一步中，我们可以选择将一个数加入路径中，或者不将其加入路径中。当路径中的数的个数大于等于2时，我们就得到了一个新的非递减子序列。
我们可以使用两个函数来解决这个问题。一个函数是 backtrack，它用于搜索所有可能的非递减子序列；另一个函数是 findSubsequences，它用于初始化回溯算法，并返回所有可能的非递减子序列。
在 backtrack 函数中，我们首先判断路径中的数的个数是否大于等于2，如果是，将其加入到结果集中。然后，我们遍历当前的选择列表，对于每个选择，我们需要进行一些判断。如果当前数小于路径中的最后一个数，我们就跳过该选择，因为这样无法得到一个非递减子序列。如果当前数已经被选择过，我们也跳过该选择，因为在同一层中，我们不能选择相同的数。为了去重，我们可以使用哈希表（C++ 中使用 unordered_set，Python 中使用 set）来记录已经选择过的数。如果当前选择符合要求，我们就将其加入到路径中，并递归调用 backtrack 函数。递归完成后，我们需要将该选择从路径中删除，以便进行下一次选择。
在 findSubsequences 函数中，我们首先初始化结果集为空集。然后，我们调用 backtrack 函数，得到所有可能的非递减子序列，并返回结果集。
C++代码
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
backtrack(nums, 0, path, res);
return res;
}
void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
if (path.size() >= 2) { // 如果路径中的数的个数大于等于2，将其加入到结果集中
res.push_back(path);
}
unordered_set<int> used; // 使用哈希表来去重
for (int i = start; i < nums.size(); i++) {
if (!path.empty() && nums[i] < path.back()) continue; // 如果当前数小于路径中的最后一个数，跳过该选择
if (used.count(nums[i])) continue; // 如果当前数已经被选择过，跳过该选择
used.insert(nums[i]); // 将当前数加入到哈希表中
path.push_back(nums[i]); // 将当前数加入到路径中
backtrack(nums, i + 1, path, res); // 递归调用 backtrack 函数
path.pop_back(); // 将当前数从路径中删除
}
}
};Python代码
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
self.backtrack(nums, 0, path, res)
return res
def backtrack(self, nums, start, path, res):
if len(path) >= 2: # 如果路径中的数的个数大于等于2，将其加入到结果集中
res.append(path[:])
used = set() # 使用集合来去重
for i in range(start, len(nums)):
if path and nums[i] < path[-1]: continue # 如果当前数小于路径中的最后一个数，跳过该选择
if nums[i] in used: continue # 如果当前数已经被选择过，跳过该选择
used.add(nums[i]) # 将当前数加入到集合中
path.append(nums[i]) # 将当前数加入到路径中
self.backtrack(nums, i + 1, path, res) # 递归调用 backtrack 函数
path.pop() # 将当前数从路径中删除
