Domain 2MediumCORE

Increasing Subsequences

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 (prevval <= currval) where the indices in the original array strictly increase. Crucially, we only care about sequences with length at least 2.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search

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:

  1. Uniqueness: The output list must not contain duplicate subsequences (e.g., if [4, 6] can be formed by two different indices of 6, it should appear once).
  2. 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 of 7 at the same recursion depth must be avoided.
  3. Size: The array length N≤15N \le 15 allows for exponential time complexity solutions (O(2N)O(2^N)).

Intuition

A brute-force approach would generate all possible subsequences (there are up to 2152^{15} subsets) and then filter them based on the increasing property. While feasible given N=15N=15, 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., if nums[i] == nums[j] and both are valid candidates at step kk, picking one is sufficient to cover all unique subsequences starting with that value).

Approach

  1. Initialize a global list result to store our final sequences.
  2. Define a recursive helper function backtrack(start_index, current_path).
  3. Base Case/Pruning: If the length of current_path is ≥2\ge 2, add a copy of it to result. Note: We don’t stop here; we continue extending because [4, 6] can become [4, 6, 7].
  4. Loop: Iterate through indices from start_index to the end of the array.
  5. Validity Check: If current_path is not empty and nums[i] < current_path[-1], skip (must be non-decreasing).
  6. 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 to current_path and recurse with index i+1i+1. Remove from path (backtrack) after returning.
  7. Return result.

Complexity Analysis

  • Time: In the worst case without duplicates, we explore a subset tree of size roughly O(2N⋅N)O(2^N \cdot N) due to copying paths and iterating through elements at each node. With duplicate pruning, it is bounded by unique subsequences times path length. Given N=15N=15, this fits well within time limits (≈30k\approx 30k operations max).
  • Space: Recursion stack depth is O(N)O(N). We store the result list and seen sets at each recursion level, which sums to roughly O(2N)O(2^N) 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.append is never triggered for length ≥2\ge 2, correctly returning [].
  • All Decreasing Input (e.g., [5, 4]): The condition val < last_val skips all extensions. Only single-element paths are explored but not added to results until len >= 2. Returns [].
  • Duplicate Values: Handled by the seen_values set inside each recursive call loop and the non-decreasing check (val <= last_val). This ensures [7, 7] is valid (since 7≤77 \le 7) but prevents generating duplicate lists in the output.