Non-decreasing Subsequences
Medium · Backtracking · Explanation and code example
Backtracking with Depth-Local Deduplication
How it works
Build subsequences by choosing later indices whose values are at least the path’s last value. At one recursion depth, choosing the same value twice would duplicate results, so keep a used set local to that depth. Equal values remain allowed at different depths.
Steps
- Save every path with length at least two.
- Try later indices that preserve nondecreasing order.
- Skip values already used at this depth and recurse.
Complexity
- Time: O(n × 2^n) including copying returned paths.
- Space: O(n²) conservative working bound for copied paths and per-depth sets, excluding output.
Things to watch for
- Use a fresh deduplication set at each depth.
- Nondecreasing allows equal values.
- Do not sort the input; the subsequence must preserve its original order.
Python code example
class Solution:
def findSubsequences(self, nums: list[int]) -> list[list[int]]:
ans = []
def dfs(s: int, path: list[int]) -> None:
if len(path) > 1:
ans.append(path)
used = set()
for i in range(s, len(nums)):
if nums[i] in used:
continue
if not path or nums[i] >= path[-1]:
used.add(nums[i])
dfs(i + 1, path + [nums[i]])
dfs(0, [])
return ans
C++ code example
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ans;
dfs(nums, 0, {}, ans);
return ans;
}
private:
void dfs(const vector<int>& nums, int s, vector<int>&& path,
vector<vector<int>>& ans) {
if (path.size() > 1)
ans.push_back(path);
unordered_set<int> used;
for (int i = s; i < nums.size(); ++i) {
if (used.contains(nums[i]))
continue;
if (path.empty() || nums[i] >= path.back()) {
used.insert(nums[i]);
path.push_back(nums[i]);
dfs(nums, i + 1, std::move(path), ans);
path.pop_back();
}
}
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.