Problem
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.
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]]
This problem could be solved by Backtracking in O(2n) time complexity. The time complexity of this solution is O(2n) because we are exploring all (almost) the subsets of the given array. And, as we know, the number of subsets of an array of length n is 2n.
Approach
To solve this problem, we can use a backtracking approach. We’ll use a recursive backtracking function that explores all possible subsequences, and we’ll maintain a set to store unique subsequences. The set will help us avoid duplicates, ensuring that we only include distinct non-decreasing subsequences in the final result.
Code Implementation
//
// main.cpp
// Non-Decreasing Subsequences
//
// Created by Himanshu on 21/01/24.
//
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void solve(vector<int>& nums, int index, vector<int>& current, set<vector<int>>& result) {
if (current.size() >= 2) {
result.insert(current); // Add the valid subsequence to the result set
}
for (int i = index; i < nums.size(); ++i) {
if (current.empty() || nums[i] >= current.back()) {
current.push_back(nums[i]);
solve(nums, i + 1, current, result); // Recursive call
current.pop_back(); // Backtrack
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> result;
vector<int> current;
solve(nums, 0, current, result);
return vector<vector<int>>(result.begin(), result.end());
}
int main() {
vector<int> nums = {4, 6, 7, 7};
vector<vector<int>> subsequences = findSubsequences(nums);
// Print the subsequences
cout << "Non-Decreasing Subsequences" << endl;
for (const auto& subsequence : subsequences) {
for (int num : subsequence) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
Output
Non-Decreasing Subsequences 4 6 4 6 7 4 6 7 7 4 7 4 7 7 6 7 6 7 7 7 7