Generate All Combinations Sum K in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Generate All Combinations Sum K with candidates [2,3,6,7]

What is the output of the following Go code that finds all unique combinations of candidates that sum to 7?

DSA Go

package main

import (
	"fmt"
)

func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var comb []int
	var backtrack func(start, target int)

	backtrack = func(start, target int) {
		if target == 0 {
			combCopy := make([]int, len(comb))
			copy(combCopy, comb)
			res = append(res, combCopy)
			return
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > target {
				continue
			}
			comb = append(comb, candidates[i])
			backtrack(i, target - candidates[i])
			comb = comb[:len(comb)-1]
		}
	}

	backtrack(0, target)
	return res
}

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

A [[2 2 3] [7]]

B [[2 3 6] [7]]

C [[2 2 2 3] [6 7]]

D [[3 3 3] [7]]

💡 Hint

Think about how the function explores combinations by including candidates multiple times and stops when the sum matches the target.

The function uses backtracking to find all combinations of candidates that sum to the target 7. It includes 2 twice and 3 once to make 7, and also includes 7 alone. Other options either have wrong sums or invalid combinations.

🧠 Conceptual

intermediate

Number of combinations for candidates [1,2,3] and target 4

How many unique combinations of candidates [1, 2, 3] sum up to 4 if each candidate can be used unlimited times?

A 5

B 7

C 4

D 6

💡 Hint

Try to list all combinations manually or think about the recursive tree of choices.

The unique combinations (in non-decreasing order) are: [1,1,1,1], [1,1,2], [1,3], [2,2]. There are 4 such combinations.

🔧 Debug

advanced

Identify the error in this combination sum code snippet

What error does the following Go code produce when trying to generate combinations summing to 5? func combinationSum(candidates []int, target int) [][]int { var res [][]int var comb []int var backtrack func(int, int) backtrack = func(start int, target int) { if target == 0 { res = append(res, comb) return } for i := start; i < len(candidates); i++ { if candidates[i] > target { continue } comb = append(comb, candidates[i]) backtrack(i, target - candidates[i]) comb = comb[:len(comb)-1] } } backtrack(0, target) return res }

A Runtime panic due to index out of range

B The code runs correctly and returns all combinations

C Syntax error due to missing return type

D The code returns references to the same slice causing all results to be identical

💡 Hint

Think about what happens when you append a slice reference to the result multiple times.

The code appends the slice 'comb' directly to 'res' without copying it. Since 'comb' is modified later, all entries in 'res' point to the same underlying slice, causing all results to be identical.

🚀 Application

advanced

Find all combinations summing to 8 with candidates [2,3,5]

What is the output of the Go function that finds all unique combinations of candidates [2,3,5] that sum to 8?

DSA Go

package main

import "fmt"

func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var comb []int
	var backtrack func(int, int)

	backtrack = func(start int, target int) {
		if target == 0 {
			combCopy := make([]int, len(comb))
			copy(combCopy, comb)
			res = append(res, combCopy)
			return
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > target {
				continue
			}
			comb = append(comb, candidates[i])
			backtrack(i, target - candidates[i])
			comb = comb[:len(comb)-1]
		}
	}

	backtrack(0, target)
	return res
}

func main() {
	candidates := []int{2, 3, 5}
	target := 8
	result := combinationSum(candidates, target)
	fmt.Println(result)
}

A [[2 2 2 2] [2 3 3] [3 5]]

B [[2 2 2 2] [3 5] [2 2 3]]

C [[2 2 3 3] [3 5] [2 2 2 2]]

D [[2 2 2 2] [2 3 3] [5 3]]

💡 Hint

Remember combinations are sorted by candidate index and candidates can be reused.

The valid combinations summing to 8 are four 2's, two 3's plus one 2, and one 3 plus one 5. The order inside each combination respects the candidate order.

🧠 Conceptual

expert

Time complexity of Generate All Combinations Sum K

What is the time complexity of generating all unique combinations of candidates that sum to target K, where each candidate can be used unlimited times?

A O(2^N) where N is the number of candidates

B O(N^K) where N is number of candidates and K is target

C Exponential in K, roughly O(K^N) due to combination explosion

D Polynomial in N and K

💡 Hint

Consider how many combinations can be formed when candidates can be repeated and sum to K.

The number of combinations grows exponentially with target K because candidates can be reused unlimited times, leading to a large search tree roughly O(N^K).

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