LeetCode 491: Non-decreasing Subsequences Solution

Master LeetCode problem 491 (Non-decreasing Subsequences), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

491. Non-decreasing Subsequences

Medium

Array Hash Table Backtracking Bit Manipulation

Problem Explanation

Explanation

To solve this problem, we can use backtracking to generate all possible non-decreasing subsequences of the given array. At each step, we have two choices: either include the current element in the subsequence or skip it. We recursively explore both choices to generate all possible subsequences that satisfy the non-decreasing condition. To avoid duplicates, we use a set to store the subsequences. Finally, we convert the set to a list and return the result.

Time complexity: O(2^N) where N is the number of elements in the input array.
Space complexity: O(2^N) for the output list of subsequences.

Solution Code

import java.util.*;

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> temp = new ArrayList<>();
        backtrack(nums, 0, temp, result);
        return new ArrayList<>(result);
    }

    private void backtrack(int[] nums, int index, List<Integer> temp, Set<List<Integer>> result) {
        if (temp.size() >= 2) {
            result.add(new ArrayList<>(temp));
        }
        
        if (index == nums.length) {
            return;
        }
        
        for (int i = index; i < nums.length; i++) {
            if (temp.isEmpty() || nums[i] >= temp.get(temp.size() - 1)) {
                temp.add(nums[i]);
                backtrack(nums, i + 1, temp, result);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 491 (Non-decreasing Subsequences)?

This page provides optimized solutions for LeetCode problem 491 (Non-decreasing Subsequences) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 491 (Non-decreasing Subsequences)?

The time complexity for LeetCode 491 (Non-decreasing Subsequences) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 491 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 491 in Java, C++, or Python.

Back to LeetCode Solutions