Problem Description

Given an array of integers nums, find all the different non-decreasing subsequences of the given array, where the length of each subsequence is at least 2.

• A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.
• The subsequences must be non-decreasing: for every pair of adjacent elements a and b in the subsequence, a <= b.
• You cannot reuse elements from the array (each element's index may only be used once per subsequence).
• The solution must not contain duplicate subsequences; that is, two subsequences are considered the same if they have the same elements in the same order.

Example:
Input: nums = [4, 6, 7, 7]
Output: [[4,6], [4,7], [4,6,7], [4,6,7,7], [6,7], [6,7,7], [7,7], [4,7,7]]

Thought Process

At first glance, the problem resembles generating all possible subsequences of an array. However, there are two major constraints: subsequences must be non-decreasing, and duplicates must be avoided.

• A brute-force approach would be to generate all possible subsequences and filter out those that are non-decreasing and of length at least 2. However, this is inefficient because the number of subsequences grows exponentially (2ⁿ).
• To improve, we can use backtracking to build subsequences step by step, only extending those that are non-decreasing. This avoids generating invalid subsequences in the first place.
• We must also avoid duplicate subsequences, especially because the input array may contain duplicate numbers. We need a way to ensure that we do not generate the same subsequence more than once.

The challenge is to efficiently explore all valid paths and avoid redundant work.

Solution Approach

We use a backtracking algorithm to systematically build all non-decreasing subsequences of length at least 2, while avoiding duplicates.

1. Backtracking Function: We define a recursive function that takes the current index and the current path (the subsequence built so far). At each step, we decide whether to include the current element in the path.
2. Non-decreasing Check: We only add the current element to the path if it is greater than or equal to the last element in the path (to maintain non-decreasing order).
3. Duplicate Avoidance: To avoid duplicate subsequences, we use a set at each recursion depth to remember which numbers we have already tried to start a subsequence with at this level. This ensures that, for any given position, we do not try the same number more than once in the same recursion layer.
4. Result Collection: Whenever our path has at least 2 elements, we add a copy of it to the final result set.
5. Base Case: The recursion ends when we have considered all elements in the array.

This approach ensures that every non-decreasing subsequence is explored, but duplicates are avoided by careful bookkeeping.

Example Walkthrough

Let's walk through the input nums = [4, 6, 7, 7]:

1. Start with an empty path and index 0. At each step, try to add nums[i] if it's non-decreasing.
2. At index 0 (4), add to the path: [4].
3. Move to index 1 (6), since 6 >= 4, path becomes [4, 6]. This is a valid subsequence (length >= 2), so add to result.
4. Continue to index 2 (7), 7 >= 6, path is [4, 6, 7], add to result.
5. At index 3 (7), 7 >= 7, path is [4, 6, 7, 7], add to result.
6. Backtrack: remove last element, consider path [4, 6], try index 3 (7), path is [4, 6, 7] (already added, but set will prevent duplicates).
7. Backtrack to [4], try index 2 (7), path is [4, 7], add to result, continue to index 3 (7), path is [4, 7, 7], add to result.
8. Repeat similar steps for starting at index 1 (6) and so on, always ensuring non-decreasing order and avoiding duplicates.

The process systematically builds all valid subsequences and the set ensures uniqueness.

Time and Space Complexity

• Brute-force Approach: Generating all possible subsequences is O(2ⁿ), and for each, checking if it's non-decreasing is O(n). This is infeasible for large arrays.
• Backtracking Approach: In the worst case (all elements equal), the number of subsequences can still be exponential, but pruning invalid paths and using sets to avoid duplicates reduces redundant work. The actual number of valid subsequences is much less than 2ⁿ in most cases.
• Space Complexity: We store all valid subsequences, so space is proportional to the number of them, which can be up to O(2ⁿ) in the worst case. The recursion stack is O(n).

Summary

The key to solving the Non-decreasing Subsequences problem is efficiently generating all valid subsequences using backtracking while avoiding duplicates with a set. By only extending non-decreasing paths and keeping track of already-used numbers at each recursion level, we avoid unnecessary work and ensure that the output contains all unique, valid subsequences of length at least 2.

Code Implementation

class Solution:
    def findSubsequences(self, nums):
        res = set()
        def backtrack(start, path):
            if len(path) >= 2:
                res.add(tuple(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])
                    backtrack(i + 1, path + [nums[i]])
        backtrack(0, [])
        return [list(seq) for seq in res]
      

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
private:
    void backtrack(vector<int>& nums, int start, vector<int>& path, set<vector<int>>& res) {
        if (path.size() >= 2) {
            res.insert(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]);
                backtrack(nums, i + 1, path, res);
                path.pop_back();
            }
        }
    }
};
      

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return new ArrayList<>(res);
    }
    private void backtrack(int[] nums, int start, List<Integer> path, Set<List<Integer>> res) {
        if (path.size() >= 2) {
            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]);
                backtrack(nums, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }
}
      

var findSubsequences = function(nums) {
    const res = new Set();
    function backtrack(start, path) {
        if (path.length >= 2) {
            res.add(path.join(','));
        }
        const used = new Set();
        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]);
                backtrack(i + 1, path.concat(nums[i]));
            }
        }
    }
    backtrack(0, []);
    return Array.from(res).map(s => s.split(',').map(Number));
};