491. Non-decreasing Subsequences

Problem Description

Given an integer array nums, return all the different possible non-decreasing subsequences of the 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]]

Example 2:

Input: nums = [4,4,3,2,1]
Output: [[4,4]]

Constraints:

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

Python Solution

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = set()
        
        def backtrack(start: int, curr: List[int]):
            if len(curr) >= 2:
                result.add(tuple(curr))
            
            for i in range(start, len(nums)):
                if not curr or nums[i] >= curr[-1]:
                    curr.append(nums[i])
                    backtrack(i + 1, curr)
                    curr.pop()
        
        backtrack(0, [])
        return [list(x) for x in result]

Java Solution

class Solution {
    private Set> result;
    private int[] nums;
    
    public List> findSubsequences(int[] nums) {
        this.result = new HashSet<>();
        this.nums = nums;
        backtrack(0, new ArrayList<>());
        return new ArrayList<>(result);
    }
    
    private void backtrack(int start, List curr) {
        if (curr.size() >= 2) {
            result.add(new ArrayList<>(curr));
        }
        
        for (int i = start; i < nums.length; i++) {
            if (curr.isEmpty() || nums[i] >= curr.get(curr.size() - 1)) {
                curr.add(nums[i]);
                backtrack(i + 1, curr);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

C++ Solution

class Solution {
private:
    set> result;
    vector nums;
    
    void backtrack(int start, vector& curr) {
        if (curr.size() >= 2) {
            result.insert(curr);
        }
        
        for (int i = start; i < nums.size(); i++) {
            if (curr.empty() || nums[i] >= curr.back()) {
                curr.push_back(nums[i]);
                backtrack(i + 1, curr);
                curr.pop_back();
            }
        }
    }
    
public:
    vector> findSubsequences(vector& nums) {
        this->nums = nums;
        vector curr;
        backtrack(0, curr);
        return vector>(result.begin(), result.end());
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var findSubsequences = function(nums) {
    const result = new Set();
    
    const backtrack = (start, curr) => {
        if (curr.length >= 2) {
            result.add(JSON.stringify(curr));
        }
        
        for (let i = start; i < nums.length; i++) {
            if (curr.length === 0 || nums[i] >= curr[curr.length - 1]) {
                curr.push(nums[i]);
                backtrack(i + 1, curr);
                curr.pop();
            }
        }
    };
    
    backtrack(0, []);
    return Array.from(result).map(x => JSON.parse(x));
};

C# Solution

public class Solution {
    private HashSet result;
    private int[] nums;
    
    public IList> FindSubsequences(int[] nums) {
        this.result = new HashSet();
        this.nums = nums;
        Backtrack(0, new List());
        
        IList> finalResult = new List>();
        foreach (string s in result) {
            finalResult.Add(s.Split(',')
                           .Where(x => !string.IsNullOrEmpty(x))
                           .Select(int.Parse)
                           .ToList());
        }
        return finalResult;
    }
    
    private void Backtrack(int start, List curr) {
        if (curr.Count >= 2) {
            result.Add(string.Join(",", curr));
        }
        
        for (int i = start; i < nums.Length; i++) {
            if (curr.Count == 0 || nums[i] >= curr[curr.Count - 1]) {
                curr.Add(nums[i]);
                Backtrack(i + 1, curr);
                curr.RemoveAt(curr.Count - 1);
            }
        }
    }
}