491. Non-decreasing Subsequences – Java Solutions Explained

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. The answer may be returned in any order.

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

Approach 1: Backtracking

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

    private void backtrack(int[] nums, int index, List singleSequence, Set> answer) {
        if (index == nums.length) {
            if (singleSequence.size() >= 2) {
                answer.add(new ArrayList<>(singleSequence));
            }
            return;
        }

        if (singleSequence.isEmpty() || singleSequence.get(singleSequence.size() - 1) <= nums[index]) {
            singleSequence.add(nums[index]);
            backtrack(nums, index + 1, singleSequence, answer);
            singleSequence.remove(singleSequence.size() - 1); // backtrack
        }

        backtrack(nums, index + 1, singleSequence, answer);
    }
}

Explanation

• We use a recursive backtracking approach to build all valid subsequences.
• At each index, we have two choices:
  • Include the current element if it maintains the non-decreasing property.
  • Skip the current element.
• We store subsequences of length at least 2 in a Set to avoid duplicates.

Complexity

• Time: O(2ⁿ × n) — We explore all subsets (2ⁿ) and store/copy sequences (up to n).
• Space: O(2ⁿ × n) — For storing subsequences in a set.

Approach 2: Bitmasking

class Solution {
    public List> findSubsequences(int[] nums) {
        int n = nums.length;
        int m = 1 << n; // Total number of combinations
        Set> answer = new HashSet<>();

        for (int bitmask = 1; bitmask < m; bitmask++) {
            List seq = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (((bitmask >> i) & 1) == 1) {
                    seq.add(nums[i]);
                }
            }

            if (seq.size() >= 2 && isNonDecreasing(seq)) {
                answer.add(seq);
            }
        }

        return new ArrayList<>(answer);
    }

    private boolean isNonDecreasing(List list) {
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i) > list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}

Explanation

• This approach generates all possible subsets using a bitmask from 1 to (2ⁿ - 1).
• For each subset:
  • We collect elements according to the bits set.
  • If the subset length is at least 2 and the elements are non-decreasing, we keep it.
• Duplicates are avoided using a Set.

Complexity

• Time: O(2ⁿ × n) — for generating subsets and checking order.
• Space: O(2ⁿ × n) — for storing valid subsequences.

Conclusion

Both solutions are valid and return the correct set of non-decreasing subsequences:

• Backtracking: More efficient in pruning unnecessary branches early during recursion.
• Bitmasking: Simpler to implement and useful for smaller arrays.

Pro Tip: Always use a Set when generating subsequences to avoid duplicates caused by repeated numbers.