491. Non-decreasing Subsequences
1. Description
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.
2. Example
Example 1
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Example 2
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
3. Constraints
- 1 <= nums.length <= 15
- -100 <= nums[i] <= 100
4. Solutions
Backtracking
n = nums.size()
Time complexity: O($2^n$n)
Space complexity: O(n)
class Solution {
public:
vector<vector<int>> findSubsequences(const vector<int> &nums) {
vector<vector<int>> sub_sequences;
vector<int> sequence;
search_sequence(nums, 0, sequence, sub_sequences);
return sub_sequences;
}
private:
void search_sequence(
const vector<int> &nums,
int i,
vector<int> &sequence,
vector<vector<int>> &sub_sequences) {
if (i == nums.size()) {
if (sequence.size() > 1) {
sub_sequences.push_back(sequence);
}
} else if (i < nums.size()) {
// skip current element; disallow skipping if it equals the last chosen value
// to avoid generating duplicate subsequences
if (sequence.empty() || nums[i] != sequence.back()) {
search_sequence(nums, i + 1, sequence, sub_sequences);
}
// take current element only if it keeps the sequence non-decreasing
if (sequence.empty() || nums[i] >= sequence.back()) {
sequence.push_back(nums[i]);
search_sequence(nums, i + 1, sequence, sub_sequences);
sequence.pop_back();
}
}
}
};