NUHMAN.com

Introduction

LeetCode 39: Combination Sum is a classic problem where you're asked to find all possible combinations of a list of candidates that sum up to a given target. Unlike typical subset sum problems, the same candidate can be used multiple times.

This problem is typically solved using backtracking, a common technique for exploring all possible combinations, and ensuring that the same candidate can be reused multiple times.

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

You may reuse the same number from candidates an unlimited number of times.

Note:

• The solution set must not contain duplicate combinations.
• The order of numbers in the combination does not matter.

Examples

go

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3], [7]]
go

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2], [2,3,3], [3,5]]
go

Input: candidates = [2], target = 1
Output: []

Approach: Backtracking

Backtracking allows us to explore all possible combinations of candidates while ensuring we do not exceed the target. The general idea is to:

1. Start with an empty combination.
2. Try adding candidates one by one while ensuring that the current combination does not exceed the target.
3. If the sum of the combination equals the target, add it to the result.
4. If the sum exceeds the target, backtrack and try the next candidate.
5. We allow candidates to be used repeatedly, so the same candidate can be added multiple times.

Go Implementation

go

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var current []int
    backtrack(candidates, target, 0, current, &res)
    return res
}

func backtrack(candidates []int, target, start int, current []int, res *[][]int) {
    if target == 0 {
        // If the target is zero, add the current combination to the result
        temp := make([]int, len(current))
        copy(temp, current)
        *res = append(*res, temp)
        return
    }

    for i := start; i < len(candidates); i++ {
        if candidates[i] > target {
            // Skip if the current candidate is greater than the remaining target
            continue
        }
        current = append(current, candidates[i])
        // Recurse with reduced target and same start index (since we can reuse elements)
        backtrack(candidates, target-candidates[i], i, current, res)
        // Backtrack: remove the last element to try other possibilities
        current = current[:len(current)-1]
    }
}

Example Walkthrough

Example 1:

go

Input: candidates = [2,3,6,7], target = 7

1. Start with current = [] and target = 7.
2. Try the first candidate 2:

• Add 2 to current: current = [2], new target = 5.
• Call backtrack recursively with target 5.

1. In the next recursive call, try adding another 2:

• Add 2 to current: current = [2, 2], new target = 3.
• Call backtrack recursively with target 3.

1. In the next recursive call, try adding another 2:

• Add 2 to current: current = [2, 2, 2], new target = 1.
• Call backtrack recursively with target 1.

1. Try adding 2 again, but the new target would be negative, so backtrack and remove the last 2.
2. Continue exploring other candidates and find the solution [2, 2, 3] and [7].

Example 2:

go

Input: candidates = [2,3,5], target = 8

1. Start with current = [] and target = 8.
2. Add 2 repeatedly until the target becomes 0 with the combination [2, 2, 2, 2].
3. Then try the combination [2, 3, 3] and [3, 5].

Time and Space Complexity

MetricComplexityTime ComplexityO(2^n)Space ComplexityO(target)

• Time Complexity: The backtracking algorithm explores all combinations that sum up to the target. In the worst case, each candidate can be used repeatedly, leading to an exponential number of recursive calls, which results in a O(2^n) time complexity where n is the length of the candidates array.
• Space Complexity: The space complexity is O(target) due to the depth of the recursive call stack, as we are tracking the current combination of numbers that sum up to the target.

Edge Cases

• Single Candidate: If the array contains only one candidate, we need to handle cases where the target is a multiple of that candidate.
• Empty Candidates: If the candidates array is empty, return an empty result.
• Target Smaller Than Smallest Candidate: If the target is smaller than the smallest candidate, no combination will be possible, and we should return an empty list.

Key Takeaways

• Backtracking is a great approach for problems like Combination Sum, where we need to explore all possible combinations.
• By allowing repetition of candidates, we modify the classic subset sum problem.
• The recursive structure of backtracking provides an elegant and straightforward solution, although the time complexity can grow exponentially in the worst case.