491. Non-decreasing Subsequences

MediumBit ManipulationArrayHash TableBacktracking

Problem Description

The problem is asking us to find all the different possible subsequences of a given array of integers nums. A subsequence is a sequence that can be obtained from another sequence by deleting some or no elements without changing the order of the remaining elements. The subsequences we are looking for should be non-decreasing, meaning each element in the subsequence is less than or equal to the subsequent element. Also, each subsequence must contain at least two elements. Unlike combinations or subsets, the order is important here, so sequences with the same elements but in different orders are considered different.

Flowchart Walkthrough

Let's analyze Leetcode 491. Non-decreasing Subsequences using the algorithm Flowchart. Here's the step-by-step approach:

Is it a graph?
- No: The problem is about finding subsequences within an array, not about nodes and edges as in graph problems.
Need to solve for kth smallest/largest?
- No: This problem involves finding all possible non-decreasing subsequences, not about finding kth smallest or largest elements.
Involves Linked Lists?
- No: The data structure involved is an array, not linked lists.
Does the problem have small constraints?
- Yes: The problem allows for exploring multiple solutions since the array length is small enough to feasibly check various combinations.
Brute force / Backtracking?
- Yes: Due to the possible small constraints and the need to explore combinations to form subsequences, brute force or backtracking is suitable. Backtracking is specifically useful for building up subsequences and abandoning them if they fail the non-decreasing condition.

Conclusion: The flowchart leads us to use a backtracking approach to solve the problem of generating all non-decreasing subsequences from the given array.

Intuition

The intuition behind the solution is to explore all possible subsequences while maintaining the non-decreasing order constraint. We can perform a depth-first search (DFS) to go through all potential subsequences. We'll start with an empty list and at each step, we have two choices:

Include the current element in the subsequence if it's greater than or equal to the last included element. This is to ensure the non-decreasing order.
Skip the current element to consider a subsequence without it.

However, to avoid duplicates, if the current element is the same as the last element we considered and decided not to include, we skip the current element. This is because including it would result in a subsequence we have already considered.

Starting from the first element, we will recursively call the DFS function to traverse the array. If we reach the end of the array, and our temporary subsequence has more than one element, we include it in our answer.

The key component of this approach is how we handle duplicates to ensure that we only record unique subsequences while performing our DFS.

Learn more about Backtracking patterns.

Solution Approach

The implementation of the solution uses a recursive approach known as Depth-First Search (DFS). Let's break down how the given Python code functions:

The function dfs is a recursive function used to perform the depth-first search, starting from the index u in the nums array. This function has the parameters u, which is the current index in the array; last, which is the last number added to the current subsequence t; and t, which represents the current subsequence being constructed.
At the beginning of the dfs function, we check if u equals the length of nums. If it does, we have reached the end of the array. At this point, if the subsequence t has more than one element (making it a valid subsequence), we append a copy of it to the answer list ans.
If the current element, nums[u], is greater than or equal to the last element (last) included in our temporary subsequence (t), we can choose to include the current element in the subsequence by appending it to t and recursively calling dfs with the next index (u + 1) and the current element as the new last.
After returning from the recursive call, the element added is popped from t to backtrack and consider subsequences that do not include this element.
Additionally, to avoid duplicates, if the current element is different from the last element, we also make a recursive call to dfs without including the current element in the subsequence t, regardless of whether it could be included under the non-decreasing criterion.
The ans list collects all valid subsequences. The initial DFS call is made with the first index (0), a value that's lower than any element of the array (-1000 in this case) as the initial last value, and an empty list as the initial subsequence.
At the end of the call to the dfs from the main function, ans will contain all possible non-decreasing subsequences of at least two elements, fulfilling the problem's requirement.

Key elements in this solution are the handling of backtracking by removing the last appended element after the recursive calls, and the checking mechanism to avoid duplicates.

The choice of the initial last value is crucial. It must be less than any element we expect in nums, ensuring that the first element can always be considered for starting a new subsequence.

Data structures:

ans: A list to store all the valid non-decreasing subsequences that have at least two elements.
t: A temporary list used to build each potential subsequence during the depth-first search.

Overall, the solution effectively explores all combinations of non-decreasing subsequences through the depth-first search while ensuring that no duplicates are generated.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the given array of integers nums = [1, 2, 2].

Initialize ans as an empty list to store our subsequences and t as an empty list to represent the current subsequence.
Start with the first element 1. Since 1 is greater than our initial last value -1000, we can include 1 in t (which is now [1]) and proceed to the next index.
At the second element 2, it's greater than the last element in t (which is 1), so we can include 2 in t (now [1, 2]) and proceed to the next element. Now our t is a valid subsequence, so we can add it to ans.
Backtrack by popping 2 from t (now [1]) and proceed without including the second element 2.
At the third element (also 2), we check if we just skipped an element with the same value (which we did). If so, we do not include this element to avoid a duplicate subsequence. If not, since 2 is equal or greater than the last element in t, we could include it in t, and add the resulting subsequence [1, 2] to ans again. But since we are skipping duplicates, we do not do this.
Instead, we proceed without including this third element 2. Since we have finished going through the array, and t has less than two elements, we don't add it to ans.
Our final ans list contains [1, 2], representing the valid non-decreasing subsequences with at least two elements.

To summarize, our DFS explores these paths:

[1] -> [1, 2] (added to ans) -> [1] (backtrack) -> [1] (skip the second 2) -> [1, 2] (skipped because it would be a duplicate) -> [1] (end of array, not enough elements).
The end result for ans is [[1, 2]].

The key part of this example is that our DFS allowed us to include the first 2, but by using the duplicate check, we did not include the second 2, ensuring our final ans list only included unique non-decreasing subsequences.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
5        def backtrack(start_index, prev_num, temp_seq):
6            # Base case: When we have traversed all elements
7            if start_index == len(nums):
8                # Save a copy of the current sequence if it's a valid subsequence
9                if len(temp_seq) > 1:
10                    subsequences.append(temp_seq[:])
11                return
12
13            # If the current number can be included in the subsequence
14            if nums[start_index] >= prev_num:
15                temp_seq.append(nums[start_index])  # Include the current number
16                backtrack(start_index + 1, nums[start_index], temp_seq)  # Recursion with the updated last element
17                temp_seq.pop()  # Backtrack and remove the last element
18          
19            # To ensure we do not add duplicates, move on if the current number equals the previous number
20            if nums[start_index] != prev_num:
21                backtrack(start_index + 1, prev_num, temp_seq)  # Recursion without the current number
22      
23        subsequences = []  # To store all the valid subsequences
24        backtrack(0, float('-inf'), [])  # Kick-off the backtracking process
25        return subsequences
26
27# The provided code does the following:
28# 1. It defines a method `findSubsequences` which accepts a list of integers.
29# 2. It uses backtracking to explore all subsequences, only adding those that are non-decreasing and have a length greater than 1 to the `subsequences` list.
30# 3. The `backtrack` helper function recursively constructs subsequences, avoiding duplicates by not revisiting the same number at each level.
31

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    private int[] sequence; // Renamed from 'nums' to 'sequence' for better clarity
6    private List<List<Integer>> subsequences; // List to store the answer subsequences
7
8    public List<List<Integer>> findSubsequences(int[] nums) {
9        this.sequence = nums; // Assign the given array to the class variable
10        subsequences = new ArrayList<>(); // Initialize the list to store subsequences
11        // Start the Depth-First Search (DFS) from index 0 with the last picked element as the smallest integer value
12        dfs(0, Integer.MIN_VALUE, new ArrayList<>());
13        return subsequences; // Return the list of subsequences
14    }
15
16    // Helper method to perform DFS
17    private void dfs(int index, int lastPicked, List<Integer> currentSubsequence) {
18        // Base case: if we've reached the end of the sequence
19        if (index == sequence.length) {
20            // Check if the current list is a subsequence with more than one element
21            if (currentSubsequence.size() > 1) {
22                // If it is, add a copy of it to the list of subsequences
23                subsequences.add(new ArrayList<>(currentSubsequence));
24            }
25            return; // End the current DFS path
26        }
27      
28        // If the current element can be picked (is greater or equal to the last picked element)
29        if (sequence[index] >= lastPicked) {
30            // Pick the current element by adding it to the currentSubsequence
31            currentSubsequence.add(sequence[index]);
32            // Continue the DFS with the next index and the new lastPicked element
33            dfs(index + 1, sequence[index], currentSubsequence);
34            // Backtrack: remove the last element added to the currentSubsequence
35            currentSubsequence.remove(currentSubsequence.size() - 1);
36        }
37      
38        // Perform another DFS to explore the possibility of not picking the current element
39        // Only if the current element isn't equal to the last picked one to avoid duplicates
40        if (sequence[index] != lastPicked) {
41            dfs(index + 1, lastPicked, currentSubsequence);
42        }
43    }
44}
45

1class Solution {
2public:
3    // Function to find all the increasing subsequences in the given vector.
4    vector<vector<int>> findSubsequences(vector<int>& nums) {
5        vector<vector<int>> subsequences;
6        vector<int> currentSubsequence;
7        backtrack(0, INT_MIN, nums, currentSubsequence, subsequences); // Assuming -1000 is a lower bound, we use INT_MIN
8        return subsequences;
9    }
10
11private:
12    // Uses backtracking to find all subsequences.
13    // u is the current index in nums.
14    // last is the last number added to the current subsequence.
15    // nums is the input array of numbers.
16    // currentSubsequence holds the current subsequence being explored.
17    // subsequences is the collection of all valid subsequences found.
18    void backtrack(int index, int lastNumber, vector<int>& nums, vector<int>& currentSubsequence, vector<vector<int>>& subsequences) {
19        if (index == nums.size()) { // Base case: reached the end of nums
20            if (currentSubsequence.size() > 1) { // If the subsequence has more than 1 element, add it to the answer.
21                subsequences.push_back(currentSubsequence);
22            }
23            return;
24        }
25        // If the current number can be added to the subsequence according to the problem definition (non-decreasing order)
26        if (nums[index] >= lastNumber) {
27            currentSubsequence.push_back(nums[index]); // Add number to the current subsequence.
28            backtrack(index + 1, nums[index], nums, currentSubsequence, subsequences); // Recursively call with next index.
29            currentSubsequence.pop_back(); // Backtrack: remove the number from current subsequence.
30        }
31        // If current number is not equal to the last number added to the subsequence, continue to next index.
32        // This avoids duplicates in the subsequences list.
33        if (nums[index] != lastNumber) { 
34            backtrack(index + 1, lastNumber, nums, currentSubsequence, subsequences); // Recursively call with next index.
35        }
36    }
37};
38

1// Function to find all the increasing subsequences in the given array.
2function findSubsequences(nums: number[]): number[][] {
3    let subsequences: number[][] = [];
4    let currentSubsequence: number[] = [];
5  
6    // Call the backtrack function to start processing the subsequences
7    backtrack(0, Number.MIN_SAFE_INTEGER, nums, currentSubsequence, subsequences); 
8    return subsequences;
9}
10
11// Uses backtracking to find all subsequences.
12// index is the current index in nums.
13// lastNumber is the last number added to the current subsequence.
14// nums is the input array of numbers.
15// currentSubsequence holds the current subsequence being explored.
16// subsequences is the collection of all valid subsequences found.
17function backtrack(index: number, lastNumber: number, nums: number[], currentSubsequence: number[], subsequences: number[][]): void {
18    if (index === nums.length) { // Base case: reached the end of nums
19        if (currentSubsequence.length > 1) { // If the subsequence has more than 1 element, add it to the answer.
20            subsequences.push([...currentSubsequence]);
21        }
22        return;
23    }
24  
25    // If the current number can be added to the subsequence according to the problem definition (non-decreasing order)
26    if (nums[index] >= lastNumber) {
27        currentSubsequence.push(nums[index]); // Add number to the current subsequence.
28        backtrack(index + 1, nums[index], nums, currentSubsequence, subsequences); // Recursively call with the next index.
29        currentSubsequence.pop(); // Backtrack: remove the number from current subsequence.
30    }
31  
32    // If current number is not equal to the last number added to the subsequence, continue to next index.
33    // This avoids duplicates in the subsequences list.
34    if (nums[index] !== lastNumber) {
35        backtrack(index + 1, lastNumber, nums, currentSubsequence, subsequences); // Recursively call with the next index.
36    }
37}
38
39// Example usage:
40const input: number[] = [4, 6, 7, 7];
41const output: number[][] = findSubsequences(input);
42console.log(output); // Output the increasing subsequences.
43

Time and Space Complexity

Time Complexity

The time complexity of the given code mainly depends on the number of recursive calls it can potentially make. At each step, it has two choices: either include the current element in the subsequence or exclude it (as long as including it does not violate the non-decreasing order constraint).

Given that we have n elements in nums, in the worst case, each element might participate in the recursion twice—once when it is included and once when it is excluded. This gives us an upper bound of O(2^n) on the number of recursive calls. However, the condition if nums[u] != last prevents some recursive calls when the previous number is the same as the current, which could lead to some pruning, but this pruning does not affect the worst-case complexity, which remains exponential.

Therefore, the time complexity of the code is O(2^n).

Space Complexity

The space complexity consists of two parts: the space used by the recursion call stack and the space used to store the combination t.

The space used by the recursion stack in the worst case would be O(n) because that's the maximum depth the recursive call stack could reach if you went all the way down including each number one after the other.

The space required for storing the combination t grows as the recursion deepens, but since the elements are only pointers or references to integers and are reused in each recursive call, this does not significantly contribute to the space complexity. However, the temporary arrays formed during the process, which are then copied to ans, could increase the storage requirements. ans itself can grow up to O(2^n) in size, in the case where every possible subsequence is valid.

Thus, the space complexity is dominated by the size of the answer array ans and the recursive call stack, leading to a total space complexity of O(n * 2^n), with n being the depth of the recursion (call stack) and 2^n being the size of the answer array in the worst case.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don't know