Combinations
mediumTime: O(C(n,k) * k)Space: O(k)
Recognize the pattern
all combinations of k numbers from 1..norder doesn't matterno duplicates
Brute force idea
Not applicable — enumeration IS the task.
Better approach
Backtracking from current index. Choose numbers ≥ last chosen to avoid duplicate combinations. When k numbers chosen, record. O(C(n,k) × k).
Key invariant
Always choosing from [start, n] produces sorted combinations, eliminating permutations of the same set.
Watch out for
Starting from 1 each time — that generates permutations. Use start = last + 1.