#491

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Non-decreasing Subsequences

Return all possible non-decreasing subsequences with at least two elements from the input array, nums.

array hash table backtracking bit manipulation

Problem Statement

Given an integer array nums, return all possible non-decreasing subsequences of the array with at least two elements. Each subsequence should be returned in any order, and subsequences must maintain the order in the original array.

You can assume that the length of nums will not exceed 15, making a backtracking solution feasible. The goal is to find subsequences where the elements do not decrease as you move through the sequence, and the solution must handle arrays with duplicates as well.

Examples

Example 1

Input: nums = [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]]

Example details omitted.

Example 2

Input: nums = [4,4,3,2,1]

Output: [[4,4]]

Example details omitted.

Constraints

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

Solution Approach

Backtracking with Hash Table

Use a backtracking approach where each potential subsequence is constructed step by step. At each step, verify if the new number can be added to the subsequence without breaking the non-decreasing rule. Use a hash table to ensure uniqueness of subsequences.

Array Scanning and Element Comparison

Iterate through the array, comparing elements to their predecessors. If the current element is greater than or equal to the last element of the subsequence, append it to the subsequence and continue exploring. This ensures all subsequences are non-decreasing.

Pruning with Early Termination

Prune unnecessary branches of the recursion tree to improve efficiency. If a subsequence has reached a length of two, store it, and skip further exploration if it cannot lead to valid subsequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the method used for backtracking and the number of unique subsequences generated. With a maximum array length of 15, the solution involves exploring potential subsequences, which can be exponential in nature. The use of hash tables ensures uniqueness of subsequences, reducing unnecessary recomputations.

What Interviewers Usually Probe

The candidate effectively applies backtracking and hash table usage to avoid redundant subsequences.
The solution scales well to the upper constraint, showing consideration of optimization techniques like pruning.
The candidate demonstrates a clear understanding of array scanning and how it helps ensure subsequences remain non-decreasing.

Common Pitfalls or Variants

Common pitfalls

Failure to track unique subsequences leading to repeated results.
Not pruning the recursion tree early enough, causing excessive computational overhead.
Incorrect handling of edge cases such as arrays with duplicate elements.

Follow-up variants

Modify the problem to allow subsequences of length one.
Expand the problem to allow strictly increasing subsequences only.
Add a constraint where subsequences must sum to a target value.

FAQ

What is the main pattern used in solving the Non-decreasing Subsequences problem?

The main pattern for solving this problem is array scanning combined with backtracking, leveraging hash tables to ensure subsequences remain unique.

How can I optimize my solution for Non-decreasing Subsequences?

Optimize by pruning unnecessary recursive branches and using hash tables to track and avoid duplicate subsequences.

Can Non-decreasing Subsequences be solved in linear time?

No, this problem involves exploring all potential subsequences, leading to an exponential time complexity depending on the array size.

What are the constraints for the Non-decreasing Subsequences problem?

The array length is constrained to be between 1 and 15, and element values are between -100 and 100.

Why is backtracking used in the Non-decreasing Subsequences problem?

Backtracking is used to explore all possible subsequences, ensuring we generate all non-decreasing subsequences of length two or more.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        def dfs(u, last, t):
            if u == len(nums):
                if len(t) > 1:
                    ans.append(t[:])
                return
            if nums[u] >= last:
                t.append(nums[u])
                dfs(u + 1, nums[u], t)
                t.pop()
            if nums[u] != last:
                dfs(u + 1, last, t)

        ans = []
        dfs(0, -1000, [])
        return ans

Continue Practicing

#691 stickers to spell word #996 number of squareful arrays #473 matchsticks to square