How do you approach Combinations?

Backtrack with a start index so combinations stay ascending.

What are common mistakes on Combinations?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

Sitelet https://gitgood.dev/coding/combinations

gitGood.dev

← Back to problems

Combinations

MediumAlgorithms

Description

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. Each combination is in ascending order, and combinations appear in lexicographic order.

Example 1

Input: n = 4, k = 2

Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Explanation: All 2-element combinations of 1..4.

Constraints

- 1 <= n <= 20 - 1 <= k <= n

Combinations: approach, complexity and pitfalls

A medium backtracking problem, graded against 7 test cases (5 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

Backtrack with a start index so combinations stay ascending.
Record a combination once its length reaches k.

The optimal approach

Show the approach: The approach

Backtracking over a start index. Recurse choosing the next number from `start` to `n`; when the path length hits `k`, record it. The start-index discipline guarantees ascending combinations in lexicographic order.

Time: O(k·C(n,k)). Space: O(k).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.