Ctrl K

All Non-Falling Subsequences

Medium
You are given an integer array values. A subsequence is what remains after deleting any elements from the array while keeping the order of the rest. Find every distinct subsequence of length at least two in which each element is greater than or equal to the one before it. Two subsequences count as the same if their values match, even when they were taken from different positions. Return them in any order; inside each subsequence, keep the elements in their array order.
Example 1
values=[3, 5, 5] → [[3, 5, 5], [3, 5], [5, 5]]

The valid picks are [3, 5], [3, 5, 5] and [5, 5]. The pair [3, 5] can be formed with either 5, but it appears in the answer only once.

Example 2
values=[9, 8, 7] → []

The values only go down, so no subsequence of two or more elements qualifies.

Example 3
values=[-2, 0, -2] → [[-2, 0], [-2, -2]]

The picks [-2, 0] and [-2, -2] qualify; [0, -2] goes down.

Constraints
  • 1 ≤ len(values) ≤ 15
  • -100 ≤ values[i] ≤ 100
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsFewest Lines Through the Dots MediumSquare-Sum Chains HardEvery Topping Combo MediumAll Distinct Card Hands MediumMost Different Pair Medium
loading Python…
Input
values=[3, 5, 5]
Expected
[[3, 5, 5], [3, 5], [5, 5]]

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.