Combinations

Medium#77combinations

You get two numbers, n and k. Return every way to choose k different numbers from 1 to n, where order does not matter: [1, 2] and [2, 1] are the same choice. Our example: n = 4, k = 3 gives 4 choices, [1, 2, 3], [1, 2, 4], [1, 3, 4] and [2, 3, 4].

77 CombinationsWalkthrough · 1×

Example: 3 of the numbers 1 to 4. Watch the root: x stops at 2, because starting at 3 leaves only 3 and 4, two numbers for three places.

[ ]11,21,2,31,2,41,31,3,422,32,3,4numbers1234path—results—
not reached yeton the way herethis stepsaved combinationnever tried: no room for the rest after itfinished, or before start: out of reach

Find every way to pick 3 of the numbers 1 to 4

01/47
restart · back · play · step
Speed
1function combine(n, k):
2 path = []
3 results = []
4 choose(1)
5 return results
6
7function choose(start):
8 if len(path) == k:
9 add copy of path to results
10 return
11 need = k - len(path)
12 for x from start to n - need + 1: // leave room
13 path.add(x)
14 choose(x + 1)
15 path.removeLast()
state
start
–
need
–
x
–
path
–
results
–
click a step to go back

← → step · space play/pause

Why it works

  1. Each call takes only numbers after the last one in the path, so every combination is built once, in increasing order, and [2, 1] never repeats [1, 2].
  2. A path is saved exactly when it holds k numbers; then removing the last number lets the loop put the next one in its place.
  3. With need places left, a start above n − need + 1 leaves fewer than need numbers, so that branch cannot finish: the loop bound skips it without going down.

Complexity

Time O(k × C(n, k)): the bound lets every path that is started reach k numbers, so the calls are at most k per answer, and each answer is a copy of k numbers. Memory O(k) besides the answer: the path and the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.