Non-decreasing Subsequences

The key idea

Build subsequences with backtracking, but at EACH recursion level keep a set of values already chosen as the next element. You cannot sort the array (that would destroy the order the answer must preserve), so duplicates can only be skipped within one level: choosing the same value twice from the same starting index produces an identical subsequence. A value smaller than the last picked element is also skipped, keeping the path non-decreasing.

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.

A subsequence is formed by deleting some (possibly zero) elements from nums while keeping the relative order of the remaining elements. A subsequence is non-decreasing when every element is greater than or equal to the one before it. The array may contain duplicates, and the returned list must not contain the same subsequence twice.

Constraints

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

Examples

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

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

Complexity

Time: O(2^n * n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →