39. Combination Sum 复习

题目

给定一个不同整数组成的数组和目标数，返回一个包含所有不重复数字的组合，这些组合的合为目标数。数组中的数字可以多次使用，你可以以任意顺序返回。

解析

f[0:n,target] = c[0] f[1:n,target-c[0]] + f[1:n,target]
就是说，在这个数组上，从前到后，要找到所有的排列组合，那么就包括包含该数，和不包含该数两种情况，同时对应的目标值不相等。

伪代码

f(cda []int, target int) [][]int

if target == 0
  return [][]int{{}}
if target < 0
  return [][]int{}
for i := range cda
  rst1 =  cda[i].append f(cda[i+1:], target-cda[i])
  rst2 = fcda[i+1:], target
return rst1 + rst2

代码

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

image.png

忽略了一个条件，数组中的数字可以多次使用。
既然可以多次使用，那么就需要对同一个数字进行多次取重，同时修改剩余目标值。

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

image.png