Understanding the Combination Sum Problem with Backtracking in Go

Problem

LeetCode 39 “Combination Sum”: find all unique combinations of candidate numbers that sum to a target value. Each candidate may be used unlimited times, and the order of numbers does not matter (combinations, not permutations).

Understanding recursion (apple analogy)

A recursive function removes the last element from a slice, recurses on the reduced slice, and stops when the slice is empty. Two perspectives are shown: the direct recursive definition and an inline expansion that repeatedly substitutes the call.

func TakeOneApple(appleGroup []int) {
    if len(appleGroup) == 0 {
        return
    }
    apple := appleGroup[len(appleGroup)-1]
    appleGroup = appleGroup[:len(appleGroup)-1]
    TakeOneApple(appleGroup)
}

Backtracking pattern

A generic backtrace function picks elements from an array, adds them to a temporary trace, recurses, then undoes the choice.

// backtrace(nums, start, trace)
func backtrace(nums []int, start int, trace []int) {
    if start == len(nums) {
        return
    }
    for i := start; i < len(nums); i++ {
        trace = append(trace, nums[i])
        backtrace(nums, i+1, trace)
        trace = trace[:len(trace)-1]
    }
}

Complete Go solution for Combination Sum

var result [][]int

func combinationSum(candidates []int, target int) [][]int {
    result = [][]int{}
    trace := []int{}
    backtrace(candidates, 0, trace, target, 0)
    return result
}

// backtrace carries the current sum and the start index.
func backtrace(candidates []int, start int, trace []int, target int, sum int) {
    if sum == target {
        tmp := make([]int, len(trace))
        copy(tmp, trace)
        result = append(result, tmp)
        return
    }
    if sum > target {
        return
    }
    for i := start; i < len(candidates); i++ {
        trace = append(trace, candidates[i])
        sum += candidates[i]
        // reuse the same index i because numbers can be chosen unlimited times
        backtrace(candidates, i, trace, target, sum)
        trace = trace[:len(trace)-1]
        sum -= candidates[i]
    }
}

Key observations

The same number may be selected repeatedly; recursion uses the same index i rather than i+1 to allow unlimited reuse.

The start index prevents generating permutations; only combinations are produced.

All candidates are positive integers, so when sum > target the branch can be pruned because further additions only increase the sum.

When sum == target a copy of the current trace is stored in result.

Solution repository: https://github.com/gofish2020/leetcode_forever