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.
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.