leetcode 第40题-组合总和二

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
思路就是当前层已经遍历过的数字就直接跳过，加速遍历

package leetcode

import (
    "sort"
)

func CombinationSum2(candidates []int, target int) [][]int {
    if len(candidates) == 0 {
        return nil
    }
    sort.Ints(candidates)
    if candidates[0] > target {
        return nil
    }

    var answer []int
    var output [][]int
    var deep func(target int, index int)
    preNum := 0 //记录一下当前层的前一个数
    deep = func(target int, index int) {
        for i := index; i >= 0; i-- {
            //如果和前一数相等直接跳过，因为前一数已经参与遍历了
            if preNum == candidates[i] {
                continue
            }
            preNum = candidates[i]
            if candidates[i] > target {
                continue
            }

            answer = append(answer, candidates[i])
            if candidates[i] == target {
                tmp := make([]int, len(answer))
                copy(tmp, answer)
                output = append(output, tmp)
                answer = answer[:len(answer)-1]
                continue
            }
            //进入下一层循环前需要重置前一数
            preNum = 0
            deep(target-candidates[i], i-1)
            preNum = answer[len(answer)-1] //遍历当前层的下一数时暂存一下当前的数字
            answer = answer[:len(answer)-1]
        }
    }

    deep(target, len(candidates)-1)
    return output
}