Combination Sum II

Medium

The problem

Given a list of positive numbers candidates (repeats allowed) and a target, return every different combination that adds up to target. Each position in the list can be used at most once, and the answer must not contain the same combination twice.

Example 1
Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Example 2
Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]
[1, 2, 2] uses two of the three 2s, and is listed once even though there are three ways to pick them.

Limits

1 ≤ candidates.length ≤ 16
1 ≤ candidates[i] ≤ 30
1 ≤ target ≤ 30
The order of combinations does not matter
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

Each number can be used once, and the input has duplicates. Combine the two ideas above.

The idea

Sort, recurse with j+1 (no reuse), skip equal siblings (j > start and same as previous), and prune when the number exceeds remaining.

Target: O(2^n) time

Go function shape

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

Reference solution

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

// CombinationSum2: each number used at most once; input has duplicates.
// Skip a value that equals its left sibling at the same depth — that branch is a repeat.
func CombinationSum2(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
			}
			if i > start && nums[i] == nums[i-1] {
				continue // duplicate sibling: same subtree as the previous one
			}
			path = append(path, nums[i])
			dfs(i+1, remain-nums[i])
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return res
}

Read the lesson: Backtracking