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 <= 1001 <= candidates[i] <= 501 <= 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
}
Last modified 4mo ago