algoadvance

Leetcode 491. Non

Problem Statement

We are given an integer array nums. The task is to 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:

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

Clarifications

1. What is the expected size of the input array?
   • Constraint: 1 <= nums.length <= 15
2. Are duplicate elements allowed in the input array?
   • Yes, duplicate elements are allowed as indicated in the example.
3. Should the solution handle very large outputs or extremely high time complexity efficiently?
   • Given the small size constraint (15 elements), we can afford a backtracking approach despite the potential high time complexity.

Strategy

• Backtracking Approach: We will use backtracking to explore all possible subsequences of the given array while maintaining the order and ensuring they are non-decreasing.
• Set for Uniqueness: To handle the uniqueness of subsequences, utilize a set to store sequences during the exploration process.
• Recursive Function: Write a recursive function that explores every element, either including it in the sequence or skipping it if it violates the non-decreasing condition.

Code

#include <vector>
#include <set>

using namespace std;

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> resultSet; // Using set to handle duplicates
        vector<int> temp; // Temporary storage for the current subsequence
        backtrack(nums, 0, temp, resultSet);
        
        // Convert the set resultSet to a vector of vectors
        return vector<vector<int>>(resultSet.begin(), resultSet.end());
    }
    
private:
    void backtrack(const vector<int>& nums, int start, vector<int>& temp, set<vector<int>>& resultSet) {
        if (temp.size() >= 2) {
            resultSet.insert(temp); // Only insert if we have a valid subsequence of at least length 2
        }
        for (int i = start; i < nums.size(); ++i) {
            if (temp.empty() || nums[i] >= temp.back()) {
                temp.push_back(nums[i]); // Include nums[i] in the subsequence
                backtrack(nums, i + 1, temp, resultSet); // Continue exploring from the next position
                temp.pop_back(); // Backtrack, remove the last element, and try another possibility
            }
        }
    }
};

Time Complexity

• Time Complexity: The time complexity of this solution is O(2^n * n) where n is the number of elements in the input array. This is because we are exploring all possible subsequences (which is 2^n) and each subsequence operation might take up to O(n) time.
• Space Complexity: O(2^n * n) for storing the subsequences in the set and the recursive stack space.

This backtracking approach ensures that we explore all possible non-decreasing subsequences and leverage a set to avoid duplicates.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?