Combinations

Return all possible combinations of k numbers chosen from 1..n.

Function signature

func Combine(n, k int) [][]int

Inputs / outputs

• n: upper bound of the range 1..n.
• k: number of elements to choose.
• Return: all size-k combinations, in lexicographic increasing order.

Example

n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Constraints

• 1 <= n <= 20

Core idea (near-solution)

Backtrack in increasing order. The start index ensures each number is used at most once and combinations stay sorted.

Invariant: path is strictly increasing, and all values are from 1..n.

Algorithm (step-by-step)

1. DFS dfs(start) with a mutable path.
2. If len(path) == k, record a copy and return.
3. For i from start to n:
   • Choose i, recurse with dfs(i+1).
   • Backtrack.
4. (Optional) Prune: if remaining numbers < k - len(path), stop early.

Correctness sketch

• Invariant: path is strictly increasing, and all values are from 1..n.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

Trace (hand walkthrough)

Example input:
n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Walk:
- start with 1 -> [1,2],[1,3],[1,4]
- start with 2 -> [2,3],[2,4]
- start with 3 -> [3,4]

Pitfalls to avoid

• Forgetting to backtrack (pop after recursion).
• Not pruning, which can cause unnecessary work.
• Returning combinations in arbitrary order if start is misused.

Complexity

• Time: O(C(n, k) * k) to build all results.
• Extra space: O(k) recursion depth (excluding output).

Implementation notes (Go)

• Use a slice path and copy it on output.
• Pruning can be implemented with a simple remaining count check.