491. Increasing Subsequences
Model: qwen3.5:9b
Topics: Depth-first Search
FAANG asked: 1
Acceptance rate: 47.7%
Problem Breakdown
We are given an integer array nums and need to return all unique increasing subsequences. An “increasing subsequence” here is defined as a non-decreasing sequence of values (prev_val <= curr_val) where the indices in the original array strictly increase. Crucially, we only care about sequences with length at least 2.
Key Constraints & Nuances:
- Uniqueness: The output list must not contain duplicate subsequences (e.g., if
[4, 6]can be formed by two different indices of6, it should appear once). - Duplicates in Input: If the input contains duplicates like
[7, 7], we treat them as valid increasing steps (prev <= curr). However, picking both to form a sequence is allowed (e.g.,[7, 7]), but forming two separate identical sequences from different indices of7at the same recursion depth must be avoided. - Size: The array length allows for exponential time complexity solutions ().
Intuition
A brute-force approach would generate all possible subsequences (there are up to subsets) and then filter them based on the increasing property. While feasible given , this is inefficient because we’d be generating duplicates that need filtering later.
The core insight here is Backtracking with Pruning. We build sequences element by element from left to right.
- At each step, if a number satisfies
current_val >= last_added_value, it’s valid to extend the current subsequence. - To handle uniqueness efficiently without checking every result against all previous ones at the end: we use a local set (
seen) within each recursive call loop. If we encounter a value that has already been processed in this specific recursion depth, we skip it. This prevents generating duplicate branches for identical values appearing consecutively or later in the array (e.g., ifnums[i] == nums[j]and both are valid candidates at step , picking one is sufficient to cover all unique subsequences starting with that value).
Approach
- Initialize a global list
resultto store our final sequences. - Define a recursive helper function
backtrack(start_index, current_path). - Base Case/Pruning: If the length of
current_pathis , add a copy of it toresult. Note: We don’t stop here; we continue extending because[4, 6]can become[4, 6, 7]. - Loop: Iterate through indices from
start_indexto the end of the array. - Validity Check: If
current_pathis not empty andnums[i] < current_path[-1], skip (must be non-decreasing). - Duplicate Handling: Maintain a set
seen_values. If we encounter a number already in this loop’s iteration, skip it to ensure unique subsequences are generated at this depth. Add the value tocurrent_pathand recurse with index . Remove from path (backtrack) after returning. - Return
result.
Complexity Analysis
- Time: In the worst case without duplicates, we explore a subset tree of size roughly due to copying paths and iterating through elements at each node. With duplicate pruning, it is bounded by unique subsequences times path length. Given , this fits well within time limits ( operations max).
- Space: Recursion stack depth is . We store the result list and
seensets at each recursion level, which sums to roughly in worst-case storage for results.
Solution
class Solution:
def findSubsequences(self, nums):
res = []
# Helper function for backtracking
def backtrack(start_index, current_path):
# If subsequence length is at least 2, it's a valid result to keep.
if len(current_path) >= 2:
res.append(list(current_path))
seen_values = set()
for i in range(start_index, len(nums)):
# Skip duplicates within the same recursion depth level
# and ensure non-decreasing order relative to previous element
val = nums[i]
if current_path: # If path is not empty (not starting a new sequence)
last_val = current_path[-1]
# Must be strictly increasing or equal for this problem's definition
# of "increasing" which allows duplicates in value but requires index increase.
# However, to avoid duplicate results like [4, 6], we check seen_values below.
if val < last_val:
continue
# Check if we've already processed this specific number at this depth level
if val not in seen_values:
current_path.append(val)
backtrack(i + 1, current_path)
current_path.pop()
seen_values.add(val)
backtrack(0, [])
return res
Edge Cases Handled
- Empty Input: The loop range
range(start_index, len(nums))handles empty arrays gracefully (loop doesn’t run), returning an empty list. - Length < 2: If the array has fewer than 2 elements or no increasing pairs exist,
res.appendis never triggered for length , correctly returning[]. - All Decreasing Input (e.g.,
[5, 4]): The conditionval < last_valskips all extensions. Only single-element paths are explored but not added to results until len >= 2. Returns[]. - Duplicate Values: Handled by the
seen_valuesset inside each recursive call loop and the non-decreasing check (val <= last_val). This ensures[7, 7]is valid (since ) but prevents generating duplicate lists in the output.