Non-decreasing Subsequences Problem

Problem

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:

1
2
3
4


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:

1
2
3
4


Input:
nums = [4,4,3,2,1]
Output:
 [[4,4]]

Solution

Method 1 – Backtracking with HashSet Deduplication

Intuition

We use backtracking to generate all possible non-decreasing subsequences, and a set at each recursion level to avoid duplicates caused by repeated numbers.

Approach

Start from each index, recursively build subsequences by adding numbers that are not less than the last added.
Use a set at each recursion level to avoid picking the same number twice at the same depth.
Add subsequences of length ≥ 2 to the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        function<void(int)> dfs = [&](int start) {
            if (path.size() > 1) res.push_back(path);
            unordered_set<int> used;
            for (int i = start; i < nums.size(); ++i) {
                if ((path.empty() || nums[i] >= path.back()) && !used.count(nums[i])) {
                    used.insert(nums[i]);
                    path.push_back(nums[i]);
                    dfs(i+1);
                    path.pop_back();
                }
            }
        };
        dfs(0);
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func findSubsequences(nums []int) [][]int {
    var res [][]int
    var path []int
    var dfs func(int)
    dfs = func(start int) {
        if len(path) > 1 {
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
        }
        used := map[int]bool{}
        for i := start; i < len(nums); i++ {
            if (len(path) == 0 || nums[i] >= path[len(path)-1]) && !used[nums[i]] {
                used[nums[i]] = true
                path = append(path, nums[i])
                dfs(i+1)
                path = path[:len(path)-1]
            }
        }
    }
    dfs(0)
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), res);
        return res;
    }
    private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        if (path.size() > 1) res.add(new ArrayList<>(path));
        Set<Integer> used = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if ((path.isEmpty() || nums[i] >= path.get(path.size()-1)) && !used.contains(nums[i])) {
                used.add(nums[i]);
                path.add(nums[i]);
                dfs(nums, i+1, path, res);
                path.remove(path.size()-1);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun findSubsequences(nums: IntArray): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        val path = mutableListOf<Int>()
        fun dfs(start: Int) {
            if (path.size > 1) res.add(path.toList())
            val used = mutableSetOf<Int>()
            for (i in start until nums.size) {
                if ((path.isEmpty() || nums[i] >= path.last()) && nums[i] !in used) {
                    used.add(nums[i])
                    path.add(nums[i])
                    dfs(i+1)
                    path.removeAt(path.size-1)
                }
            }
        }
        dfs(0)
        return res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


use std::collections::HashSet;
impl Solution {
    pub fn find_subsequences(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let mut path = vec![];
        fn dfs(nums: &Vec<i32>, start: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
            if path.len() > 1 { res.push(path.clone()); }
            let mut used = HashSet::new();
            for i in start..nums.len() {
                if (path.is_empty() || nums[i] >= *path.last().unwrap()) && !used.contains(&nums[i]) {
                    used.insert(nums[i]);
                    path.push(nums[i]);
                    dfs(nums, i+1, path, res);
                    path.pop();
                }
            }
        }
        dfs(&nums, 0, &mut path, &mut res);
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

Complexity

⏰ Time complexity: O(2^n) in the worst case (all numbers are the same).
🧺 Space complexity: O(n) for the recursion stack and result.

Non-decreasing Subsequences Problem#

Problem#

Examples#

Solution#

Method 1 – Backtracking with HashSet Deduplication#

Intuition#

Approach#

Code#

Complexity#