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.
1import java.util.*;
2
The Java implementation uses bitmasking to generate subsequences, with a `HashSet` to handle duplicates. Each bit in the mask corresponds to an element, and their presence in each subsequence is determined iteratively. Valid subsequences are added to the result after ensuring the non-decreasing order.