40. Combination Sum II

Medium

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

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

Note: The solution set must not contain duplicate combinations.

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]
]

Constraints:

• 1 <= candidates.length <= 100

• 1 <= candidates[i] <= 50

• 1 <= target <= 30

解題

func combinationSum2(candidates []int, target int) [][]int {
    ans := make([][]int, 0) // 放答案的陣列
    sort.Ints(candidates) // 先排序

    var dfs func(int, int, []int) 
    dfs = func(index int, sum int, cur []int) {
        if sum == target {
            ans = append(ans, append([]int{}, cur...)) // 直接append cur 會錯
            return
        }

        if index >= len(candidates) { return }
        if sum > target { return }

        for i := index; i < len(candidates); i++ {
            if i > index && candidates[i] == candidates[i-1] {
                continue 
            }
            dfs(i+1, sum+candidates[i], append(cur, candidates[i]))
        }
    }

    dfs(0, 0, []int{})

    return ans
}