Sponsored
Sponsored
This approach leverages a recursive backtracking method to explore all possible subsequences. The process involves recursively adding elements to the current subsequence and proceeding to the next elements only if they maintain a non-decreasing order. This approach ensures each subsequence is visited and non-decreasing ones are retained. To avoid duplication, a set or unique list is used for storing resulting subsequences.
Time Complexity: O(2^n), where n is the number of elements in the array, since each element can either be included or not in a subsequence.
Space Complexity: O(n*2^n) for storing all subsequences in the worst case.
1from typing import List
2
3def findSubsequences(nums: List[int]) -> List[List[int]]:
4 def backtrack(start, path):
5 if len(path) > 1:
6 res.add(tuple(path))
7 for i in range(start, len(nums)):
8 if not path or path[-1] <= nums[i]:
9 backtrack(i + 1, path + [nums[i]])
10
11 res = set()
12 backtrack(0, [])
13 return [list(seq) for seq in res]
14
15# Example usage
16nums = [4,6,7,7]
17print(findSubsequences(nums))The code defines a recursive function `backtrack` that explores all potential subsequences starting at each index of the array. It uses a set `res` to avoid duplicates. Subsequences are formed by gradually building and checking them to ensure they are non-decreasing before adding.
This approach utilizes a bitmask technique to generate all possible subsequences iteratively. Each number's presence in a given subsequence is represented by a corresponding bit in a binary number, allowing for a systematic generation of potential subsequences. By iterating over all possible binary representations, the algorithm constructs and evaluates subsequences for their non-decreasing nature before storing them.
Time Complexity: O(n * 2^n) due to checking each subsequence for validity.
Space Complexity: O(n * 2^n) for storing all subsequences.
1var findSubsequences = function(nums) {
In JavaScript, this code leverages a `Set` to store unique sequences and iterates over the `mask` value representing all subsequences. The inner loop checks each bit of `mask` and includes the corresponding element if it fits the subsequence. It ensures non-decreasing order by comparing the last element of `sequence`.