Given two integers n and k, return every way to choose k distinct numbers from the range 1 to n. A combination is unordered, so [1,2] and [2,1] count as the same one. The answer may be in any order.
- 1 <= n <= 20
- 1 <= k <= n
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One brute force is to generate all 2^n subsets and keep the ones of size k, which wastes time on subsets of the wrong size. Backtracking builds combinations in increasing order, so each set is produced exactly once. At every step we choose the next number from start onward. If the numbers left are not enough to reach size k, the branch can never succeed, so we cut the loop short.
Algorithm
- Define
backtrack(start, path). Iflen(path) == k, record a copy. - Let
need = k - len(path). Loopxfromstartton - need + 1. - Append
x, recurse withstart = x + 1, then pop it.
O(C(n, k) * k)Space: O(k) recursion depth, excluding the outputn - need + 1.class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res, path = [], []Β def backtrack(start): if len(path) == k: res.append(path[:]) return need = k - len(path) for x in range(start, n - need + 2): # leave room for the remaining picks path.append(x) backtrack(x + 1) path.pop()Β backtrack(1) return res