Skip to main content

Non-Decreasing Subsequences

Problem Statement​

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.

Examples​

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<=151 <= nums.length <= 15
  • −100<=nums[i]<=100-100 <= nums[i] <= 100

Algorithm​

  1. Use depth-first search (DFS) to explore all subsequences.
  2. Start from the beginning of the array and for each element, either include it in the current subsequence if it maintains non-decreasing order or skip it.
  3. Use a set to ensure that each element is used only once at each level of recursion to avoid duplicates.
  4. Add the current subsequence to the result if it has at least two elements.

Code​

Python​

class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def dfs(start, path):
if len(path) > 1:
res.append(path)
used = set()
for i in range(start, len(nums)):
if nums[i] not in used and (not path or nums[i] >= path[-1]):
used.add(nums[i])
dfs(i + 1, path + [nums[i]])

res = []
dfs(0, [])
return res

C++​

class Solution {
public:
vector<vector<int>> ans;

void dfs(vector<int>& nums, vector<int>& temp, int index) {
if (temp.size() > 1) ans.push_back(temp);

unordered_set<int> used;
for (int i = index; i < nums.size(); i++) {
if ((temp.empty() || temp.back() <= nums[i]) && used.find(nums[i]) == used.end()) {
temp.push_back(nums[i]);
dfs(nums, temp, i + 1);
temp.pop_back();
used.insert(nums[i]);
}
}
}

vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<int> temp;
dfs(nums, temp, 0);
return ans;
}
};

Java​

import java.util.*;

class Solution {
List<List<Integer>> ans = new ArrayList<>();

public void dfs(int[] nums, List<Integer> temp, int index) {
if (temp.size() > 1) ans.add(new ArrayList<>(temp));

Set<Integer> used = new HashSet<>();
for (int i = index; i < nums.length; i++) {
if ((temp.isEmpty() || temp.get(temp.size() - 1) <= nums[i]) && used.add(nums[i])) {
temp.add(nums[i]);
dfs(nums, temp, i + 1);
temp.remove(temp.size() - 1);
}
}
}

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

JavaScript​

var findSubsequences = function (nums) {
const res = [];

const dfs = (start, path) => {
if (path.length > 1) {
res.push([...path]);
}
const used = new Set();
for (let i = start; i < nums.length; i++) {
if (
!used.has(nums[i]) &&
(path.length === 0 || nums[i] >= path[path.length - 1])
) {
used.add(nums[i]);
path.push(nums[i]);
dfs(i + 1, path);
path.pop();
}
}
};

dfs(0, []);
return res;
};