Problem Statement
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
- Note: A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
Example Inputs
Example 1:
Problem Solution
Approach
To find all non-decreasing subsequences of the given array with at least two elements, we can use a recursive backtracking approach. The key challenges are:
- Maintaining Non-decreasing Order: Ensure that each subsequence is non-decreasing by only adding elements that are greater than or equal to the last element in the current subsequence.
- Handling Duplicates: Avoid adding duplicate subsequences by using a mechanism to track and skip duplicates during the recursion.
Steps
-
Initialize:
- Create a
Set to store unique subsequences. Since JavaScript Set cannot store arrays directly, we'll store their stringified versions.
- Start with an empty
current subsequence and begin processing from the first element.
-
Recursive Backtracking Function (backtrack):
-
Base Case: If we've considered all elements, check if the current subsequence has at least two elements. If so, add its stringified version to the Set.
-
Decision Point: For each element starting from the current index:
- Include the Element: If the
current subsequence is empty or the current element is greater than or equal to the last element in current, add it to current and recurse for the next index.
- Exclude the Element: Simply move to the next index without adding the current element.
- Skip Duplicates: To avoid duplicates, skip elements that are the same as the previous one at the same recursion depth.
-
Post-processing:
- Convert the
Set of stringified subsequences back into an array of arrays before returning the result.
Time & Space Complexity
- Time Complexity: O(2^n), where n is the number of elements in
nums. This is because each element has two choices: include or exclude.
- Space Complexity: O(n) for the recursion stack and O(k * n) for storing the subsequences, where k is the number of valid subsequences.
Code Snippet
Dry Run
Let's perform a dry run with nums = [4, 6, 7, 7].
-
Initial Call: backtrack(0)
-
First Level (start = 0):
- i = 0: Include 4
current = [4]- Recurse:
backtrack(1)
-
Second Level (start = 1):
- i = 1: Include 6
current = [4, 6]- Add
[4,6] to ansSet
- Recurse:
backtrack(2)
-
Third Level (start = 2):
- i = 2: Include 7
current = [4, 6, 7]- Add
[4,6,7] to ansSet
- Recurse:
backtrack(3)
-
Fourth Level (start = 3):
- i = 3: Include 7
current = [4, 6, 7, 7]- Add
[4,6,7,7] to ansSet
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [4,6,7]
- i = 3: Exclude 7 (since it's the same as previous and already considered)
- Skip to avoid duplicate
- Backtrack to
current = [4,6]
-
Back to Third Level (start = 2):
- i = 2: Exclude 7
current = [4,6]- Recurse:
backtrack(3)
- i = 3: Include 7
current = [4,6,7]- Add
[4,6,7] to ansSet (already exists)
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [4,6]
- i = 3: Exclude 7 (duplicate)
- Skip
- Backtrack to
current = [4,6]
- Backtrack to
current = [4]
-
Back to Second Level (start = 1):
- i = 1: Exclude 6
current = [4]- Recurse:
backtrack(2)
- i = 2: Include 7
current = [4,7]- Add
[4,7] to ansSet
- Recurse:
backtrack(3)
- i = 3: Include 7
current = [4,7,7]- Add
[4,7,7] to ansSet
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [4,7]
- i = 3: Exclude 7 (duplicate)
- Skip
- Backtrack to
current = [4,7]
- Backtrack to
current = [4]
- i = 2: Exclude 7 (duplicate at this level)
- i = 3: Exclude 7 (duplicate)
- Backtrack to
current = [4]
-
Back to First Level (start = 0):
- i = 0: Exclude 4
current = []- Recurse:
backtrack(1)
- i = 1: Include 6
current = [6]- Recurse:
backtrack(2)
- i = 2: Include 7
current = [6,7]- Add
[6,7] to ansSet
- Recurse:
backtrack(3)
- i = 3: Include 7
current = [6,7,7]- Add
[6,7,7] to ansSet
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [6,7]
- i = 3: Exclude 7 (duplicate)
- Skip
- Backtrack to
current = [6,7]
- Backtrack to
current = [6]
- i = 2: Exclude 7
current = [6]- Recurse:
backtrack(3)
- i = 3: Include 7
current = [6,7]- Add
[6,7] to ansSet (already exists)
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [6,7]
- i = 3: Exclude 7 (duplicate)
- Skip
- Backtrack to
current = [6]
- Backtrack to
current = [6]
- Backtrack to
current = []
- i = 1: Exclude 6
- i = 2: Include 7
current = [7]- Recurse:
backtrack(3)
- i = 3: Include 7
current = [7,7]- Add
[7,7] to ansSet
- Recurse:
backtrack(4)
- End of Array: Backtrack to
current = [7,7]
- i = 3: Exclude 7 (duplicate)
- Skip
- Backtrack to
current = [7,7]
- Backtrack to
current = [7]
- i = 2: Exclude 7 (duplicate at this level)
- i = 3: Exclude 7 (duplicate)
- Backtrack to
current = []
-
Final Subsets: [["4,6"], ["4,6,7"], ["4,6,7,7"], ["4,7"], ["4,7,7"], ["6,7"], ["6,7,7"], ["7,7"]]
Complexity Analysis
Optimized Time and Space
The recursive backtracking approach efficiently explores all possible subsequences while avoiding duplicates through the use of a Set. Although the number of possible subsequences can be large (up to 2^n), pruning and skipping duplicates help in managing the computation.
- Optimized Time Complexity: O(2^n), where n is the number of elements in
nums.
- Optimized Space Complexity: O(n) for the recursion stack and O(k * n) for storing the unique subsequences, where k is the number of valid subsequences.
Conclusion
Generating all non-decreasing subsequences of a given array, especially when duplicates are present, is a classic problem that demonstrates the effectiveness of recursive backtracking combined with strategies to handle duplicates. By carefully choosing whether to include or exclude each element and ensuring that the subsequences maintain a non-decreasing order, we can efficiently explore all valid combinations. Utilizing data structures like Set in JavaScript helps in managing and eliminating duplicate subsequences, ensuring that the final output contains only unique results. This approach not only solves the problem at hand but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization.