LeetCode Problem 491

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Backtracking, Bit Manipulation

Solution

LeetCode 491 - Non-decreasing Subsequences

Problem Understanding

The problem gives us an integer array nums and asks us to return every distinct subsequence that is non-decreasing and has length at least two.

A subsequence is formed by deleting zero or more elements from the array without changing the relative order of the remaining elements. Unlike subarrays, subsequences do not need to be contiguous.

A non-decreasing subsequence means every next element is greater than or equal to the previous one. For example:

• [4,6,7] is valid because 4 <= 6 <= 7
• [4,7,7] is valid because equal values are allowed
• [6,4] is invalid because the sequence decreases

The important detail is that the output must contain only distinct subsequences. Since the input array may contain duplicate values, different index selections can generate identical subsequences. We must avoid returning duplicates.

The constraints are relatively small:

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

Since the array length is at most 15, the total number of subsequences is at most 2^15 = 32768, which is manageable. This strongly suggests that an exhaustive search or backtracking solution is appropriate.

Several edge cases are important:

• Arrays with all decreasing values, such as [5,4,3,2], produce very few valid subsequences.
• Arrays with duplicates, such as [4,6,7,7], can generate duplicate subsequences if not handled carefully.
• Arrays with all equal values, such as [1,1,1], require careful duplicate elimination.
• Arrays of length 1 can never produce a valid subsequence because the minimum required length is 2.

Approaches

Brute Force Approach

The brute force solution generates every possible subsequence of the array and then filters the valid ones.

Since each element can either be included or excluded, there are 2^n possible subsequences. For every generated subsequence, we check:

1. Whether its length is at least 2
2. Whether it is non-decreasing
3. Whether it has already been added to the answer

A hash set can be used to eliminate duplicates by storing subsequences as tuples.

This approach is correct because it examines every possible subsequence. However, it is inefficient because it explores many invalid subsequences and repeatedly checks monotonicity after construction.

Optimal Backtracking Approach

The better solution builds subsequences incrementally using backtracking.

The key observation is that we do not need to generate invalid subsequences. While constructing a subsequence, we only append a number if it maintains the non-decreasing property.

Another important insight is duplicate handling. At each recursion level, we use a local set to track which values have already been used. This prevents generating duplicate subsequences from repeated values at the same depth.

For example, in [4,6,7,7], when exploring candidates after [4,6], choosing the first 7 and the second 7 separately would produce duplicate subsequences. The local set prevents this duplication.

This pruning significantly reduces redundant work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(2^n * n)	Generates all subsequences, then validates each
Optimal	O(2^n)	O(2^n * n)	Backtracking with pruning and duplicate elimination

Algorithm Walkthrough

1. Initialize an empty result list that will store all valid subsequences.
2. Create a recursive backtracking function that takes two parameters:

• start_index, the next position we are allowed to explore
• current_sequence, the subsequence currently being built

3. At the beginning of each recursive call, check whether current_sequence has length at least 2. If it does, append a copy to the result.
4. Create a local hash set called used. This set tracks which values have already been chosen at the current recursion depth.
5. Iterate through the array starting from start_index.
6. For each candidate number:

• Skip it if it has already been used at this recursion level. This prevents duplicate subsequences.
• Skip it if adding it would violate the non-decreasing property.

7. If the number is valid:

• Add it to used
• Append it to current_sequence
• Recurse using the next index
• Remove the number afterward to backtrack

8. Continue until all recursive paths have been explored.

Why it works

The algorithm explores every possible subsequence that preserves array order. The non-decreasing condition is enforced during construction, so every generated subsequence is valid. The local used set guarantees that duplicate values at the same recursion depth are considered only once, preventing duplicate subsequences from entering the result.

Python Solution

from typing import List

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(start_index: int, current_sequence: List[int]) -> None:
            if len(current_sequence) >= 2:
                result.append(current_sequence[:])

            used = set()

            for i in range(start_index, len(nums)):
                current_num = nums[i]

                if current_num in used:
                    continue

                if current_sequence and current_num < current_sequence[-1]:
                    continue

                used.add(current_num)

                current_sequence.append(current_num)
                backtrack(i + 1, current_sequence)
                current_sequence.pop()

        backtrack(0, [])

        return result

The implementation follows the recursive backtracking strategy directly.

The result list stores all valid subsequences.

The backtrack function recursively builds subsequences. Whenever the current subsequence has at least two elements, it is copied into the result list. A copy is necessary because lists are mutable and will later be modified during backtracking.

The used set is recreated at every recursion level. This is extremely important because duplicate elimination should only apply within the same depth of recursion. Using a global set would incorrectly remove valid subsequences.

The condition:

if current_sequence and current_num < current_sequence[-1]:

ensures the subsequence remains non-decreasing.

After adding a number, recursion continues with i + 1, guaranteeing that indices remain in increasing order and subsequence ordering is preserved.

Finally, pop() restores the previous state so other recursive branches can be explored.

Go Solution

package main

func findSubsequences(nums []int) [][]int {
	var result [][]int
	var currentSequence []int

	var backtrack func(int)

	backtrack = func(startIndex int) {
		if len(currentSequence) >= 2 {
			sequenceCopy := make([]int, len(currentSequence))
			copy(sequenceCopy, currentSequence)
			result = append(result, sequenceCopy)
		}

		used := make(map[int]bool)

		for i := startIndex; i < len(nums); i++ {
			currentNum := nums[i]

			if used[currentNum] {
				continue
			}

			if len(currentSequence) > 0 &&
				currentNum < currentSequence[len(currentSequence)-1] {
				continue
			}

			used[currentNum] = true

			currentSequence = append(currentSequence, currentNum)
			backtrack(i + 1)
			currentSequence = currentSequence[:len(currentSequence)-1]
		}
	}

	backtrack(0)

	return result
}

The Go implementation mirrors the Python solution closely.

Since Go slices are references to underlying arrays, we must explicitly create a copy before appending a subsequence to result. Otherwise, later modifications during backtracking would corrupt previously stored subsequences.

The used set is implemented using map[int]bool.

Go does not distinguish between nil and empty slices in a way that matters for this problem, so the implementation naturally handles empty subsequences correctly.

Integer overflow is not a concern because the input range is very small.

Worked Examples

Example 1

Input:

nums = [4,6,7,7]

Initial call:

current_sequence = []
start_index = 0

The recursive exploration proceeds as follows.

Step	Current Sequence	Next Choice	Result Added
1	[]	4	No
2	[4]	6	No
3	[4,6]	7	[4,6]
4	[4,6,7]	7	[4,6,7]
5	[4,6,7,7]	End	[4,6,7,7]
6	[4]	7	[4,7]
7	[4,7]	7	[4,7,7]
8	[]	6	No
9	[6]	7	No
10	[6,7]	7	[6,7]
11	[6,7,7]	End	[6,7,7]
12	[]	7	No
13	[7]	7	No
14	[7,7]	End	[7,7]

Final 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]

The algorithm begins with the first 4.

Step	Current Sequence	Next Choice	Valid?
1	[]	4	Yes
2	[4]	4	Yes
3	[4,4]	3	No
4	[4,4]	2	No
5	[4,4]	1	No

All decreasing values are skipped because they violate the non-decreasing rule.

Final output:

[[4,4]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	Every element may be included or excluded
Space	O(2^n * n)	Result storage dominates complexity

The recursion tree can contain up to 2^n states because every element has two possibilities, include or exclude. The duplicate pruning reduces redundant exploration but does not change the worst case asymptotic complexity.

The recursion stack itself uses O(n) space, but the result list can store exponentially many subsequences, each of length up to n, so total storage becomes O(2^n * n).

Test Cases

from typing import List

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(start_index: int, current_sequence: List[int]) -> None:
            if len(current_sequence) >= 2:
                result.append(current_sequence[:])

            used = set()

            for i in range(start_index, len(nums)):
                current_num = nums[i]

                if current_num in used:
                    continue

                if current_sequence and current_num < current_sequence[-1]:
                    continue

                used.add(current_num)

                current_sequence.append(current_num)
                backtrack(i + 1, current_sequence)
                current_sequence.pop()

        backtrack(0, [])

        return result

solution = Solution()

# Basic example with duplicates
assert sorted(solution.findSubsequences([4, 6, 7, 7])) == sorted([
    [4, 6],
    [4, 6, 7],
    [4, 6, 7, 7],
    [4, 7],
    [4, 7, 7],
    [6, 7],
    [6, 7, 7],
    [7, 7]
])

# Strictly decreasing array
assert sorted(solution.findSubsequences([4, 4, 3, 2, 1])) == sorted([
    [4, 4]
])

# Single element array
assert solution.findSubsequences([1]) == []

# All equal elements
assert sorted(solution.findSubsequences([1, 1, 1])) == sorted([
    [1, 1],
    [1, 1, 1]
])

# Negative numbers
assert sorted(solution.findSubsequences([-1, -1, 0])) == sorted([
    [-1, -1],
    [-1, 0],
    [-1, -1, 0]
])

# Already increasing array
assert sorted(solution.findSubsequences([1, 2, 3])) == sorted([
    [1, 2],
    [1, 3],
    [2, 3],
    [1, 2, 3]
])

# Mixed increasing and decreasing
assert sorted(solution.findSubsequences([3, 1, 2])) == sorted([
    [1, 2]
])

# Duplicate handling stress test
assert sorted(solution.findSubsequences([1, 2, 2])) == sorted([
    [1, 2],
    [1, 2, 2],
    [2, 2]
])

Test	Why
[4,6,7,7]	Standard example with duplicates
[4,4,3,2,1]	Mostly decreasing values
[1]	Minimum array size
[1,1,1]	Heavy duplicate handling
[-1,-1,0]	Negative numbers and duplicates
[1,2,3]	Fully increasing array
[3,1,2]	Mixed ordering
[1,2,2]	Duplicate subsequence elimination

Edge Cases

One important edge case is an array with only one element, such as [5]. Since the problem requires subsequences of length at least two, no valid answer exists. A buggy implementation might accidentally include single-element subsequences. This solution avoids that issue by adding sequences to the result only when their length is at least 2.

Another critical edge case involves duplicate values, such as [1,1,1]. Without careful duplicate handling, the same subsequence could be generated multiple times through different index combinations. The per-level used set ensures that identical values are explored only once at each recursion depth, eliminating duplicate outputs cleanly.

A third important edge case is a strictly decreasing array like [5,4,3,2]. In this scenario, almost every attempted extension violates the non-decreasing condition. The implementation handles this efficiently by checking:

current_num < current_sequence[-1]

before recursion, preventing invalid subsequences from ever being explored.

Another subtle edge case is negative numbers mixed with duplicates, such as [-2,-1,-1]. Some implementations incorrectly assume values are positive or mishandle equality comparisons. This solution relies only on standard integer comparisons, so negative values and equal values are handled naturally and correctly.