Pattern Recognition Drill

#78 — Combinations

Medium Backtracking

The Problem

Given n and k, return all combinations of k numbers from 1 to n.

What approach would you use?

Think about it before scrolling down.

Key Signals

'Combinations' → order doesn't matter → avoid duplicates by always picking in increasing order
Start each recursive call from the next number

Backtracking

From index start, choose next number, recurse with start+1. Collect when path has k elements. O(C(n,k)).

Common Trap

The key to avoiding duplicates: always pick in ascending order (start from last_picked + 1).

← #77 #79 →