Combination Sum II - Go Solution

LeetCode

— 2 min read

Solving the LeetCode "Combination Sum II" Problem in Go

Difficulty: Medium | Tags: Array, Backtracking

Introduction

This problem requires finding all unique combinations of numbers in a given array that sum up to a target value, where each number can only be used once in a combination. The solution must avoid duplicate combinations, making backtracking an ideal approach.

Problem Analysis

Given an array of candidate numbers and a target, we need to find all unique combinations where the sum equals the target. Each candidate can only be used once per combination, and the solution must not include duplicate combinations. For example, in the input [10,1,2,7,6,1,5] with target 8, valid combinations include [1,1,6], [1,2,5], [1,7], and [2,6].

Solution Approach

The solution involves using backtracking to explore all possible combinations while avoiding duplicates. We first sort the array to handle duplicates efficiently. During the backtracking process, we skip over duplicate elements to ensure unique combinations. The algorithm recursively builds combinations, adding valid ones to the result when the target is reached.

Go Implementation


package main
import (
"fmt"
"sort"
)
func combinationSum2(candidates []int, target int) [][]int {
    var result [][]int
    sort.Ints(candidates)
    backtrack(&result, candidates, []int{}, target, 0)
    return result
}
func backtrack(result *[][]int, candidates, current []int, target, start int) {
    if target == 0 {
        temp := make([]int, len(current))
        copy(temp, current)
        *result = append(*result, temp)
        return
    }
    for i := start; i < len(candidates); i++ {
        if i > start && candidates[i] == candidates[i-1] {
            continue
        }
        if candidates[i] > target {
            break
        }
        current = append(current, candidates[i])
        backtrack(result, candidates, current, target-candidates[i], i+1)
        current = current[:len(current)-1]
    }
}
func main() {
    candidates1 := []int{10, 1, 2, 7, 6, 1, 5}
    target1 := 8
    fmt.Println(combinationSum2(candidates1, target1))
    candidates2 := []int{2, 5, 2, 1, 2}
    target2 := 5
    fmt.Println(combinationSum2(candidates2, target2))
}

Complexity Analysis

The time complexity is O(2^n), where n is the number of candidates, as in the worst case, we explore all possible combinations. The space complexity is O(n) due to the recursion stack, where n is the depth of the recursion tree.

Testing and Examples

Test cases include the provided examples and edge cases such as an empty array, a single-element array, and cases where no combinations are possible. For instance:

  • Input: [10,1,2,7,6,1,5], target 8 → Output: [[1,1,6], [1,2,5], [1,7], [2,6]]
  • Input: [2,5,2,1,2], target 5 → Output: [[1,2,2], [5]]

Best Practices and Tips

Key takeaways include sorting the array to handle duplicates efficiently, using backtracking to explore combinations, and avoiding duplicate combinations by skipping over repeated elements. Always ensure to copy the current combination before adding it to the result to prevent modification of shared slices.

Read more