40. Combination Sum II #

Problem #

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Summary #

Given an array candidates and a target number target, find all combinations in candidates where the numbers sum to target.

Each number in candidates may only be used once in each combination.

Solution Approach #

• The problem asks for all combinations whose total sum is sum, and the combinations need to be deduplicated. This problem is an enhanced version of Problem 39. In Problem 39, elements can be reused (duplicate elements can be used an unlimited number of times), while in this problem elements can only be used a limited number of times. Since duplicate elements exist, and each element can only be used once (duplicate elements can only be used a limited number of times)
• This problem is similar to Problem 47.

Code #

package leetcode

import (
	"sort"
)

func combinationSum2(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	c, res := []int{}, [][]int{}
	sort.Ints(candidates) // This is the key deduplication logic
	findcombinationSum2(candidates, target, 0, c, &res)
	return res
}

func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) {
	if target == 0 {
		b := make([]int, len(c))
		copy(b, c)
		*res = append(*res, b)
		return
	}
	for i := index; i < len(nums); i++ {
		if i > index && nums[i] == nums[i-1] { // This is the key deduplication logic; do not take duplicate numbers in this iteration, but a later loop may take duplicate numbers
			continue
		}
		if target >= nums[i] {
			c = append(c, nums[i])
			findcombinationSum2(nums, target-nums[i], i+1, c, res)
			c = c[:len(c)-1]
		}
	}
}