LeetCode 491 – Non-decreasing Subsequences (Algorithm Explanation and Multi-language Solutions)

Problem: Given an integer array nums, return all different increasing subsequences of length at least two. The subsequence does not need to be contiguous, and duplicate numbers are allowed as long as the sequence is non‑decreasing.

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.

Analysis: The problem is solved by depth‑first search (DFS) that builds subsequences incrementally. At each recursion level we keep a Set (or hash table) to skip duplicate values at the same depth, ensuring uniqueness of results. The search proceeds only when the next number is ≥ the last element of the current path.

Java solution:

public List<List<Integer>> findSubsequences(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(ans, nums, new ArrayList<>(), 0);
    return ans;
}
private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> path, int index) {
    if (path.size() > 1) ans.add(new ArrayList<>(path));
    Set<Integer> set = new HashSet<>();
    for (int i = index; i < nums.length; i++) {
        if (!set.add(nums[i])) continue;
        if (path.isEmpty() || nums[i] >= path.get(path.size() - 1)) {
            path.add(nums[i]);
            dfs(ans, nums, path, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

C++ solution:

vector<vector<int>> findSubsequences(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> path;
    dfs(ans, nums, path, 0);
    return ans;
}
void dfs(vector<vector<int>>& ans, const vector<int>& nums, vector<int>& path, int index) {
    if (path.size() > 1) ans.emplace_back(path);
    unordered_set<int> s;
    for (int i = index; i < nums.size(); ++i) {
        if (s.count(nums[i])) continue;
        s.insert(nums[i]);
        if (path.empty() || nums[i] >= path.back()) {
            path.push_back(nums[i]);
            dfs(ans, nums, path, i + 1);
            path.pop_back();
        }
    }
}

C solution (LeetCode style):

void dfs(int** ans, int* path, int count, int* nums, int numsSize,
         int* returnSize, int** returnColumnSizes, int index) {
    if (count > 1) {
        ans[*returnSize] = malloc(count * sizeof(int));
        memcpy(ans[*returnSize], path, count * sizeof(int));
        (*returnColumnSizes)[(*returnSize)++] = count;
    }
    int set[201] = {0};
    for (int i = index; i < numsSize; ++i) {
        int key = nums[i] + 100;
        if (set[key]) continue;
        set[key] = 1;
        if (count == 0 || nums[i] >= path[count - 1]) {
            path[count++] = nums[i];
            dfs(ans, path, count, nums, numsSize, returnSize, returnColumnSizes, i + 1);
            --count;
        }
    }
}

Python solution:

def findSubsequences(self, nums: List[int]) -> List[List[int]]:
    ans = []
    path = []
    def dfs(index):
        if len(path) > 1:
            ans.append(path[:])
        seen = set()
        for i in range(index, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            if not path or nums[i] >= path[-1]:
                path.append(nums[i])
                dfs(i + 1)
                path.pop()
    dfs(0)
    return ans