40. Combination Sum II 组合总和2

题目

给定一个数组 candidates 和一个目标数 target。找到使数组中数相加等于 target 的所有组合。每个数字只能使用一次。不能包含重复解

解析

上一个问题的简化版本，每个数字只能使用一次，就表明每次只有两种情况，使用这个数字和不使用这个数字。

伪代码

if candidates == 0 || target <= 0
  return nil
rst1 = combinationSum2(candidates[1:], target)
rst2 = combinationSum2(candidates[1:], target-candidates[0])
rst2 = append(rst2, candidates[0])
if target == candidates[0]
  rst3 = [][]int{{candidates[0]}}
return append(rst1,rst2, rst3)

错误代码1

func combinationSum2(candidates []int, target int) [][]int {
    if len(candidates) == 0 || target <=0 {
        return nil
    }
    var rst [][]int
    rst1 := combinationSum2(candidates[1:],target)
    rst2 := combinationSum2(candidates[1:],target-candidates[0])
    for i :=range rst2 {
        rst2[i]=append(rst2[i], candidates[0])
    }
    if target == candidates[0] {
        rst=append(rst, []int{candidates[0]})
    }
    rst=append(rst, rst1...)
    rst=append(rst, rst2...)
    return rst
}

image.png

出现了重复，为什么会重复呢。因为递归时，不包含 i 找到的解法和 包含 i 找到的解法可能相同，也就是说，找到的不含 i 的解法在附加上 i 之后，和含 i 的解法相同了。 也就是说，我们不包含1 时，找到一个解法 7 1。 当包含 1 时，找到一个解法 7。这两解法是相同的。如何解决这个问题？？
可以参考 Sum，将这个问题转化为一个数最多使用 n 次。

1. 将数组进行排序。
2. 每次迭代时，找到下一个不相同的数作为边界，在相同的数字上进行叠加。
3. 排序后，能更快的打断不可能的条件。

代码

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    return combination(candidates,target)
}

func combination(candidates []int, target int) [][]int {
    if len(candidates) == 0 || target < candidates[0] {
        return nil
    }
    
    next:=0
    for ;next < len(candidates); next++ {
        if candidates[next] != candidates[0] {
            break
        }
    }
    
    var rsts [][]int
    var suf []int
    for i:=0;i<=next;i++ {
        if target < candidates[0]*i {
            break
        }
        if target == candidates[0]*i {
            rsts=append(rsts, suf)
            break
        }
        rst := combination(candidates[next:], target-candidates[0]*i)
        for t := range rst {
            rst[t]=append(rst[t], suf...)
        }
        rsts=append(rsts, rst...)
        
        suf=append(suf,candidates[0])
    }
    return rsts
}

image.png