Solving the LeetCode "Combinations" Problem in Go

Difficulty: Medium | Tags: Backtracking

Introduction

The "Combinations" problem requires generating all possible combinations of size k from numbers 1 to n. This is a classic backtracking problem that helps in understanding recursion and combinatorial generation.

Problem Analysis

Given n = 4 and k = 2, the output should be all unique pairs of numbers between 1 and 4. The solution must avoid duplicates like [1,2] and [2,1], as order does not matter in combinations. The problem constraints ensure that n and k are within manageable limits for backtracking.

Solution Approach

We use a backtracking approach to explore all possible combinations. Starting from the first number, we recursively build combinations by including or excluding numbers, ensuring no duplicates and maintaining the order. The recursion stops when the combination reaches size k.

Go Implementation

func combine(n int, k int) [][]int {
    var result [][]int
    var backtrack func(start int, current []int)
    backtrack = func(start int, current []int) {
        if len(current) == k {
            temp := make([]int, k)
            copy(temp, current)
            result = append(result, temp)
            return
        }
        for i := start; i <= n; i++ {
            current = append(current, i)
            backtrack(i+1, current)
            current = current[:len(current)-1]
        }
    }
    backtrack(1, []int{})
    return result
}

Complexity Analysis

The time complexity is O(C(n, k)), where C(n, k) is the binomial coefficient, as we generate all combinations. The space complexity is O(k) for the recursion stack, excluding the output storage.

Testing and Examples

Test case 1: n = 4, k = 2 should return [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]. Test case 2: n = 1, k = 1 should return [[1]]. Edge cases include k = n, which returns a single combination of all numbers.

Best Practices and Tips

Always make a copy of the current combination before adding it to the result to avoid reference issues. Optimize by pruning unnecessary branches early if possible. Practice similar backtracking problems to build intuition.