Medium Backtrack+Prune Backtracking
In plain English: List all ways to choose k numbers from 1 to n (order does not matter).
To avoid duplicates, always pick elements in increasing order — start each recursive call from the next number after the last picked.
Prompt
Given n and k, return all combinations of k numbers from 1 to n.
Try to write it from scratch before scrolling down.
Solution
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
# prune: not enough numbers left
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
# Test: combine(4, 2) == [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]