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
Solution 1
PythonJavaC++Go
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(code-box)
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) {
ans.add(new ArrayList<>(t));
}
return;
}
if (nums[u] >= last) {
t.add(nums[u]);
dfs(u + 1, nums[u], t);
t.remove(t.size() - 1);
}
if (nums[u] != last) {
dfs(u + 1, last, t);
}
}
}(code-box)
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);
}
};(code-box)
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
}(code-box)
