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.
1#include <vector>
2#include <set>
3
4using namespace std;
5
6void backtrack(int start, vector<int>& nums, vector<int>& path, set<vector<int>>& res) {
7 if (path.size() > 1) {
8 res.insert(path);
9 }
10 for (int i = start; i < nums.size(); ++i) {
11 if (path.empty() || path.back() <= nums[i]) {
12 path.push_back(nums[i]);
13 backtrack(i + 1, nums, path, res);
14 path.pop_back();
15 }
16 }
17}
18
19vector<vector<int>> findSubsequences(vector<int>& nums) {
20 set<vector<int>> res;
21 vector<int> path;
22 backtrack(0, nums, path, res);
23 return vector<vector<int>>(res.begin(), res.end());
24}
25
26// Example usage
27// vector<int> nums = {4,6,7,7};
28// vector<vector<int>> result = findSubsequences(nums);The C++ implementation uses a helper function `backtrack` to recursively construct subsequences. A set is employed to store the subsequences, ensuring uniqueness. The function iterates over the elements to form valid subsequences that maintain the non-decreasing condition by checking the last element of `path`.
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`.