Generate All Combinations Sum K in DSA Go

Mental Model

Find all groups of numbers from a list that add up exactly to a target number by trying each number and exploring further choices.

Analogy: Imagine you have a box of different colored beads and want to pick some beads so their total weight equals a target weight. You try picking one bead, then try adding others until you reach the target or go over.

Candidates: [2, 3, 6, 7]
Target: 7
Start -> [] (empty combination)
Try 2 -> [2]
Try 2 again -> [2 -> 2]
Try 3 -> [2 -> 2 -> 3]
Backtrack when sum > 7

Dry Run Walkthrough

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

Goal: Find all combinations of candidates that sum to 7

Step 1: Start with empty combination [] and sum 0

[] sum=0

Why: We begin with no numbers chosen

Step 2: Add 2 to combination: [2], sum=2

[2] sum=2

Why: Try first candidate to see if it leads to target

Step 3: Add 2 again: [2 -> 2], sum=4

[2 -> 2] sum=4

Why: We can reuse numbers, so try 2 again

Step 4: Add 3: [2 -> 2 -> 3], sum=7

[2 -> 2 -> 3] sum=7

Why: Sum matches target, record this combination

Step 5: Backtrack: remove last 3, try next candidate 6 at [2 -> 2]

[2 -> 2] sum=4

Why: Try other candidates after backtracking

Step 6: Add 6: [2 -> 2 -> 6], sum=10 (exceeds target)

[2 -> 2 -> 6] sum=10

Why: Sum too big, backtrack immediately

Step 7: Backtrack to [2], try 3: [2 -> 3], sum=5

[2 -> 3] sum=5

Why: Try next candidate after backtracking

Step 8: Add 3 again: [2 -> 3 -> 3], sum=8 (exceeds target)

[2 -> 3 -> 3] sum=8

Why: Sum too big, backtrack

Step 9: Backtrack to [2], try 6: [2 -> 6], sum=8 (exceeds target)

[2 -> 6] sum=8

Why: Sum too big, backtrack

Step 10: Backtrack to [], try 3: [3], sum=3

[3] sum=3

Why: Try next candidate from start

Step 11: Add 3 again: [3 -> 3], sum=6

[3 -> 3] sum=6

Why: Try reusing 3

Step 12: Add 3 again: [3 -> 3 -> 3], sum=9 (exceeds target)

[3 -> 3 -> 3] sum=9

Why: Sum too big, backtrack

Step 13: Backtrack to [3 -> 3], try 6: [3 -> 3 -> 6], sum=12 (exceeds target)

[3 -> 3 -> 6] sum=12

Why: Sum too big, backtrack

Step 14: Backtrack to [3], try 6: [3 -> 6], sum=9 (exceeds target)

[3 -> 6] sum=9

Why: Sum too big, backtrack

Step 15: Backtrack to [], try 6: [6], sum=6

[6] sum=6

Why: Try next candidate

Step 16: Add 6 again: [6 -> 6], sum=12 (exceeds target)

[6 -> 6] sum=12

Why: Sum too big, backtrack

Step 17: Backtrack to [], try 7: [7], sum=7

[7] sum=7

Why: Sum matches target, record this combination

Result:

[2 -> 2 -> 3] sum=7
[7] sum=7
Answer: [[2, 2, 3], [7]]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func combinationSum(candidates []int, target int) [][]int {
	var result [][]int
	var combination []int

	var backtrack func(start, target int)
	backtrack = func(start, target int) {
		if target == 0 {
			// Found valid combination
			comboCopy := make([]int, len(combination))
			copy(comboCopy, combination)
			result = append(result, comboCopy)
			return
		}
		if target < 0 {
			// Exceeded target, stop exploring
			return
		}

		for i := start; i < len(candidates); i++ {
			// Choose candidates[i]
			combination = append(combination, candidates[i])
			// Explore further with reduced target
			backtrack(i, target - candidates[i])
			// Undo choice (backtrack)
			combination = combination[:len(combination)-1]
		}
	}

	backtrack(0, target)
	return result
}

func main() {
	candidates := []int{2, 3, 6, 7}
	target := 7
	results := combinationSum(candidates, target)
	for _, combo := range results {
		fmt.Print("[")
		for i, val := range combo {
			if i > 0 {
				fmt.Print(", ")
			}
			fmt.Print(val)
		}
		fmt.Println("]")
	}
}

if target == 0 {

Check if current combination sums exactly to target

comboCopy := make([]int, len(combination)) copy(comboCopy, combination) result = append(result, comboCopy)

Save a copy of the valid combination

if target < 0 { return }

Stop exploring if sum exceeds target

for i := start; i < len(candidates); i++ {

Try each candidate starting from current index

combination = append(combination, candidates[i])

Add candidate to current combination

backtrack(i, target - candidates[i])

Recurse with updated target and allow reuse of current candidate

combination = combination[:len(combination)-1]

Remove last candidate to backtrack

Output

[2, 2, 3]

[7]

Complexity Analysis

Time: O(2^n) because each candidate can be chosen or not, leading to exponential combinations

Space: O(k) where k is the depth of recursion and size of current combination

vs Alternative: Compared to brute force checking all subsets, this prunes paths early when sum exceeds target, saving time

Edge Cases

Empty candidates list

Returns empty result since no combinations possible

DSA Go

for i := start; i < len(candidates); i++ {

Target is zero

Returns one empty combination [] as valid

DSA Go

if target == 0 {

Candidates contain duplicates

Duplicates are allowed and can appear multiple times in combinations

DSA Go

backtrack(i, target - candidates[i])

When to Use This Pattern

When asked to find all combinations that sum to a target with repeated use of elements, use backtracking to explore choices and prune sums exceeding target.

Common Mistakes

Mistake: Not backtracking properly by forgetting to remove last added element
Fix: Always remove last element after recursive call to restore state

Mistake: Starting loop from 0 each time causing duplicate combinations
Fix: Start loop from current index to avoid duplicates and allow reuse

Summary

Find all groups of numbers that add up to a target by trying each candidate and exploring further choices recursively.

Use when you need all possible combinations summing to a target, allowing repeated elements.

The key is to explore candidates recursively, backtrack when sum exceeds target, and save combinations when sum matches target.

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. All unique combinations of numbers that add up to K

B. The largest number less than K

C. The sum of all numbers from 1 to K

D. The product of all numbers that divide K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that add exactly to the target sum K.

2. Step 2: Clarify what combinations mean

   Combinations mean groups of numbers where order does not matter, and each number can be used once or multiple times depending on problem rules.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option A

4. Quick Check:

   Combinations sum K = unique sets adding to K [OK]

Hint: Focus on sums that exactly equal K, ignoring order [OK]

Common Mistakes:

• Confusing combinations with permutations
• Looking for a single sum instead of all combinations
• Ignoring the target sum K

2. Which of the following Go function signatures is correct for a function that generates all combinations summing to K from a slice of integers?

easy

A. func combinationSum(nums []int, target int) int

B. func combinationSum(nums int, target []int) []int

C. func combinationSum(nums []int, target int) []int

D. func combinationSum(nums []int, target int) [][]int

Solution

1. Step 1: Identify input parameters

   The function should take a slice of integers and a target integer sum.

2. Step 2: Identify return type

   It should return a slice of slices of integers, representing all combinations.

3. Final Answer:

   func combinationSum(nums []int, target int) [][]int -> Option D

4. Quick Check:

   Input slice and target int, output slice of int slices [OK]

Hint: Return type must hold multiple combinations ([][]int) [OK]

Common Mistakes:

• Swapping parameter types
• Returning a single slice instead of slice of slices
• Returning an int instead of combinations

3. What is the output of the following Go code snippet?

func main() {
    nums := []int{2, 3, 6, 7}
    target := 7
    result := combinationSum(nums, target)
    fmt.Println(result)
}

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

medium

A. [[2 2 3] [7]]

B. [[2 3 6] [7]]

C. [[3 3 3] [7]]

D. [[2 2 2 3] [7]]

Solution

1. Step 1: Understand backtracking logic

   The function tries combinations starting from each index, allowing reuse of numbers, and collects paths summing to target.

2. Step 2: Trace combinations for target 7

   Possible sums are [2,2,2,3] and [7] because 2+2+2+3=9 is incorrect, so check carefully: 2+2+2+3=9 (too big), so that is invalid. The actual combinations are [2,2,3] (2+2+3=7) and [7].

3. Step 3: Verify options

   [[2 2 2 3] [7]] shows [2 2 2 3] which sums to 9, invalid. [[2 2 3] [7]] shows [2 2 3] and [7], which is correct.

4. Final Answer:

   [[2 2 3] [7]] -> Option A

5. Quick Check:

   Backtracking finds [2 2 3] and [7] sums [OK]

Hint: Look for combinations that sum exactly to 7 using given nums [OK]

Common Mistakes:

• Including invalid sums like [2 3 6]
• Ignoring reuse of numbers
• Confusing order of elements

4. Identify the bug in this Go function for generating combinations summing to K:

func combinationSum(nums []int, target int) [][]int {
    var res [][]int
    var backtrack func(start, target int, path []int)
    backtrack = func(start, target int, path []int) {
        if target == 0 {
            res = append(res, path)
            return
        }
        for i := start; i < len(nums); i++ {
            if nums[i] > target {
                continue
            }
            backtrack(i, target-nums[i], append(path, nums[i]))
        }
    }
    backtrack(0, target, []int{})
    return res
}

medium

A. The target check should be target < 0 instead of target == 0

B. The loop should start from 0 every time, not from start

C. Appending path directly causes shared slice reference issues

D. The function should return a single slice, not slice of slices

Solution

1. Step 1: Check how path is appended to result

   Appending path directly stores the reference, causing all results to point to the same underlying array.

2. Step 2: Fix by copying path before appending

   Make a copy of path slice before appending to res to avoid shared references.

3. Final Answer:

   Appending path directly causes shared slice reference issues -> Option C

4. Quick Check:

   Copy path before append to avoid shared slice bugs [OK]

Hint: Always copy slices before appending to result [OK]

Common Mistakes:

• Appending slice references directly
• Incorrect loop start index
• Wrong base case condition

5. Given a list of integers with duplicates, how would you modify the combination sum algorithm to generate all unique combinations summing to K without duplicates? Choose the best approach.

hard

A. Use a map to store sums and ignore duplicates after generation

B. Sort the list and skip duplicate numbers during recursion

C. Allow duplicates freely and filter results at the end

D. Increase target by 1 to avoid duplicates

Solution

1. Step 1: Sort the input list

   Sorting helps group duplicates together so they can be skipped during recursion.

2. Step 2: Skip duplicates in recursion

   When iterating, skip numbers equal to the previous one at the same recursion level to avoid duplicate combinations.

3. Final Answer:

   Sort the list and skip duplicate numbers during recursion -> Option B

4. Quick Check:

   Sorting + skipping duplicates = unique combinations [OK]

Hint: Sort input and skip duplicates while recursing [OK]

Common Mistakes:

• Filtering duplicates after generating all combinations
• Not sorting input before recursion
• Changing target incorrectly