Non-decreasing Subsequences

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an integer array nums, return every **distinct** subsequence of length at least 2 whose elements are non-decreasing from left to right. A subsequence keeps elements in their original relative order but may skip elements. Two subsequences are the same if they contain the same values in the same order, even if they were picked from different indices; list each such sequence only once. Each subsequence must be written in its original order. The list of subsequences may be returned in any order.

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]]
`[4,7]` can be formed from either 7, but it is listed once.
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
Only the two leading 4s form a non-decreasing pair.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems