Combination Sum - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Combination Sum" Problem in Go

Difficulty: Medium | Tags: Array, Backtracking

Introduction

The "Combination Sum" problem requires finding all unique combinations of numbers from a given array that sum up to a target value. This problem is a classic example of backtracking, where we explore all possible combinations and prune the search space when the sum exceeds the target.

Problem Analysis

Given a list of distinct integers, we need to find all combinations where the sum of the numbers equals the target. The same number can be used multiple times, and the order of numbers in the combination does not matter. For example, if the input is [2,3,6,7] and the target is 7, the valid combinations are [2,2,3] and [7].

Solution Approach

We use a backtracking approach to explore all possible combinations. Starting from the first candidate, we recursively add candidates to the current combination and subtract their value from the target. If the target reaches zero, we add the combination to the result. If the target becomes negative, we backtrack and try the next candidate.

Go Implementation


func combinationSum(candidates []int, target int) [][]int {
    var result [][]int
    var backtrack func(int, int, []int)
    backtrack = func(start int, remaining int, current []int) {
        if remaining == 0 {
            temp := make([]int, len(current))
            copy(temp, current)
            result = append(result, temp)
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining {
                continue
            }
            current = append(current, candidates[i])
            backtrack(i, remaining - candidates[i], current)
            current = current[:len(current)-1]
        }
    }
    backtrack(0, target, []int{})
    return result
}

Complexity Analysis

The time complexity is O(N^(T/M + 1)), where N is the number of candidates, T is the target, and M is the smallest candidate. This is because, in the worst case, we explore all possible combinations. The space complexity is O(T/M) due to the recursion stack depth.

Testing and Examples

Test Case 1: Input: [2,3,6,7], target = 7. Output: [[2,2,3],[7]].
Test Case 2: Input: [2,3,5], target = 8. Output: [[2,2,2,2],[2,3,3],[3,5]].
Test Case 3: Input: [2], target = 1. Output: [].

Best Practices and Tips

1. Sort the candidates first to optimize pruning.
2. Use a helper function for cleaner recursion.
3. Avoid duplicate combinations by passing the start index.
4. Make a copy of the current combination before adding it to the result.

Read more