# 491. Non-decreasing Subsequences

## Description

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

## Solutions

• class Solution {
private int[] nums;
private List<List<Integer>> ans;

public List<List<Integer>> findSubsequences(int[] nums) {
this.nums = nums;
ans = new ArrayList<>();
dfs(0, -1000, new ArrayList<>());
return ans;
}

private void dfs(int u, int last, List<Integer> t) {
if (u == nums.length) {
if (t.size() > 1) {
}
return;
}
if (nums[u] >= last) {
dfs(u + 1, nums[u], t);
t.remove(t.size() - 1);
}
if (nums[u] != last) {
dfs(u + 1, last, t);
}
}
}

• class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
dfs(0, -1000, t, nums, ans);
return ans;
}

void dfs(int u, int last, vector<int>& t, vector<int>& nums, vector<vector<int>>& ans) {
if (u == nums.size()) {
if (t.size() > 1) ans.push_back(t);
return;
}
if (nums[u] >= last) {
t.push_back(nums[u]);
dfs(u + 1, nums[u], t, nums, ans);
t.pop_back();
}
if (nums[u] != last) dfs(u + 1, last, t, nums, ans);
}
};

• class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def dfs(u, last, t):
if u == len(nums):
if len(t) > 1:
ans.append(t[:])
return
if nums[u] >= last:
t.append(nums[u])
dfs(u + 1, nums[u], t)
t.pop()
if nums[u] != last:
dfs(u + 1, last, t)

ans = []
dfs(0, -1000, [])
return ans


• func findSubsequences(nums []int) [][]int {
var ans [][]int
var dfs func(u, last int, t []int)
dfs = func(u, last int, t []int) {
if u == len(nums) {
if len(t) > 1 {
ans = append(ans, slices.Clone(t))
}
return
}
if nums[u] >= last {
t = append(t, nums[u])
dfs(u+1, nums[u], t)
t = t[:len(t)-1]
}
if nums[u] != last {
dfs(u+1, last, t)
}
}
var t []int
dfs(0, -1000, t)
return ans
}