Combinations
mediumTime: O(C(n,k) * k)Space: O(k)
Signals to notice
all combinations of k numbers from 1..norder doesn't matterno duplicates
Brute force first
Not applicable — enumeration IS the task.
The key insight
Backtracking from current index. Choose numbers ≥ last chosen to avoid duplicate combinations. When k numbers chosen, record. O(C(n,k) × k).
What must stay true
Always choosing from [start, n] produces sorted combinations, eliminating permutations of the same set.
Easy way to go wrong
Starting from 1 each time — that generates permutations. Use start = last + 1.