Non-decreasing Subsequences

Non-decreasing Subsequences

What is this problem about?

The Non-decreasing Subsequences problem asks you to find all distinct non-decreasing subsequences of an integer array of length ≥ 2. Subsequences are non-contiguous (can skip elements) but must preserve original order. This coding problem uses backtracking with duplicate detection to enumerate all valid subsequences.

Why is this asked in interviews?

Yahoo, Amazon, and Google ask this to test backtracking with deduplication — specifically, avoiding duplicate subsequences when the same value appears multiple times at the same recursion level. The array, hash table, backtracking, and bit manipulation interview pattern is applied, and the deduplication logic is the main challenge.

Algorithmic pattern used

Backtracking with level-based deduplication. At each recursion level, use a local set to track which values have been tried as the next element (to avoid duplicate branches). For each eligible element (≥ last added value), if not tried at this level yet, add it to the current subsequence, recurse, then backtrack. Record the current subsequence when it has length ≥ 2.

Example explanation

Array: [4, 6, 7, 7]. Find all non-decreasing subsequences of length ≥ 2. Starting from index 0 with no constraint: try 4 (mark 4 tried). From index 1, last=4: try 6, 7, 7... subsequences: [4,6],[4,7],[4,6,7],[4,6,7,7]... then try 6 at root. Result includes [6,7],[6,7,7],[7,7] etc. Total distinct valid subsequences.

Common mistakes candidates make

• Sorting the array before backtracking (destroys the original order constraint).
• Not using a local set per recursion level (causes duplicate subsequences).
• Confusing subsequence (non-contiguous, order-preserving) with subarray (contiguous).
• Recording subsequences of length 1 (must require at least 2 elements).

Interview preparation tip

Subsequence backtracking problems that require deduplication without sorting use a level-local set. Unlike permutation deduplication (which sorts and skips equal adjacent elements), here you can't sort. The local set at each level tracks which values have been used as the starting element for that recursion depth. Practice this pattern on "find all distinct subsets with order preserved" variants — the local deduplication set is the key differentiator from standard subset generation.