Combination Sum

Medium

The problem

Given different positive numbers in candidates and a target, return every unique combination of candidates that adds up to target. You may use the same number as many times as you like. Two combinations are the same if they use each number the same number of times; order does not matter.

Example 1
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
2 + 2 + 3 = 7 and 7 = 7.
Example 2
Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Limits

1 ≤ candidates.length ≤ 10
2 ≤ candidates[i] ≤ 40, all different
1 ≤ target ≤ 40
Combinations and the numbers inside them may be in any order
If nothing works return an empty list

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A number can be reused. How do you reuse it without generating the same combination in a different order?

The idea

DFS(start, remaining): for j ≥ start choose candidate j and recurse with the SAME j (reuse allowed); stop when remaining is 0 or negative.

Target: O(2^t) roughly

Go function shape

func combinationSum(candidates []int, target int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CombinationSum: combinations that add up to target; each number reusable.
// Sorting lets us prune: once a number overshoots, all later ones do too.
func CombinationSum(candidates []int, target int) [][]int {
	nums := append([]int(nil), candidates...)
	sort.Ints(nums)
	res := [][]int{}
	path := []int{}
	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if remain == 0 {
			res = append(res, append([]int(nil), path...))
			return
		}
		for i := start; i < len(nums); i++ {
			if nums[i] > remain {
				break // prune: sorted, so every later number is too big as well
			}
			path = append(path, nums[i])
			dfs(i, remain-nums[i]) // i, not i+1: the same number may be reused
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

Read the lesson: Backtracking