Non-decreasing Subsequences

medium array hash set backtracking

Problem

Given an integer array nums, return all distinct non-decreasing subsequences with length ≥ 2. You may return the answer in any order.

Inputnums = [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]]

Dedup is over subsequences, not positions — picking the first 7 or second 7 first yields the same sequence.

nums

def find_subsequences(nums):
    out = []
    def dfs(i, path):
        if len(path) >= 2: out.append(path[:])
        used = set()
        for j in range(i, len(nums)):
            if path and nums[j] < path[-1]: continue
            if nums[j] in used: continue
            used.add(nums[j])
            path.append(nums[j])
            dfs(j + 1, path)
            path.pop()
    dfs(0, [])
    return out

function findSubsequences(nums) {
  const out = [];
  function dfs(i, path) {
    if (path.length >= 2) out.push(path.slice());
    const used = new Set();
    for (let j = i; j < nums.length; j++) {
      if (path.length && nums[j] < path[path.length - 1]) continue;
      if (used.has(nums[j])) continue;
      used.add(nums[j]);
      path.push(nums[j]);
      dfs(j + 1, path);
      path.pop();
    }
  }
  dfs(0, []);
  return out;
}

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

class Solution {
    vector<vector<int>> out;
    vector<int> a;
    void dfs(int i, vector<int>& path) {
        if ((int)path.size() >= 2) out.push_back(path);
        unordered_set<int> used;
        for (int j = i; j < (int)a.size(); j++) {
            if (!path.empty() && a[j] < path.back()) continue;
            if (used.count(a[j])) continue;
            used.insert(a[j]);
            path.push_back(a[j]);
            dfs(j + 1, path);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        a = nums; vector<int> p; dfs(0, p); return out;
    }
};

Explanation

We build subsequences by walking the array left to right and deciding which elements to keep. The dfs(i, path) function extends the current path using elements from index i onward, and records path whenever its length is at least 2.

To stay non-decreasing, we only add nums[j] if it is not smaller than the last element in path (nums[j] < path[-1] is skipped). This guarantees every saved sequence never goes down.

The tricky part is avoiding duplicate subsequences. Note we cannot just sort, because the order of the original array matters. Instead, at each level we keep a used set of values already tried at that depth. If the same value appears again at this level, we skip it — that prevents producing the same sequence twice from equal numbers in different positions.

Example: nums = [4, 6, 7, 7]. Starting at the first 7 versus the second 7 at the same level would both make "7,7"-style sequences, so the per-level used set blocks the repeat. The result includes [7,7] once, not twice.

After exploring a choice we pop it to backtrack, so each branch tries a fresh continuation.

Time: O(2^n · n) Space: O(n) recursion + output