leetcode的Combination Sum题补充切片的传递

Combination Sum以go 切片的传递

内容：
回溯法。
切片切为形参，为值传递。如果需要引用传递，要加指针。
切片作为append参数是引用传递。
前拷贝copy方法，要求dst的len大于len(src)。
append则没有这个要求，只要在cap以内。
区别make()切片的len参数和cap参数。
回溯法的curRes无论传值，还是传址的，都要清理数据，以准备下次迭代。

题目：

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

思路：

• 回溯法的递归和非递规实现
• 重点：切片是个引用传递，curRes加入res需要拷贝。但是作为参数传递是值传递，需要传res *[][]int
• 执行前拷贝要给足len。
• 回溯递归调用前后，要注意curRes的添加和清理。虽然无论是递归方法的值传递不会改变curRes（引用一定会改变），但至少循环当中的app()就改变了curRes。
• 重点：去掉重复解的方法，在递归中加一个形参idx。允许重复从idx遍历，不允许重复从idx+1遍历。

解：（这个解有重复解）

func combinationSum(candidates []int, target int) [][]int {
    res := make([][]int,0)
    var curRes []int
    backtraceCombinationSum(candidates,target,curRes,&res)
    return res
}

func backtraceCombinationSum(candidates []int, target int,curRes []int,res *[][]int)  {
    if target<0{
        return
    }
    if target==0{
        curRes1 := make([]int,len(curRes))
        copy(curRes1,curRes)
        *res = append(*res,curRes1)
        return
    }

    for _,elem := range candidates{
        curRes = append(curRes,elem)
        backtraceCombinationSum(candidates,target-elem,curRes,res)
        curRes = curRes[0:len(curRes)-1]
    }
}

解：（修复了重复解问题）

func combinationSum(candidates []int, target int) [][]int {
    res := make([][]int,0)
    var curRes []int
    backtraceCombinationSum(candidates,target,0,curRes,&res)
    return res
}

func backtraceCombinationSum(candidates []int, target int,idx int,curRes []int,res *[][]int)  {
    //必须要引用传递*res
    if target<0{
        return
    }
    if target==0{
        //需要深复制，copy不同于append，要给足len
        curRes1 := make([]int,len(curRes))
        copy(curRes1,curRes)
        *res = append(*res,curRes1)
        return
    }

    for i := idx;i<len(candidates);i++{
        curRes = append(curRes,candidates[i])
        backtraceCombinationSum(candidates,target-candidates[i],i,curRes,res)
        //需要清理数据，准备下次迭代
        curRes = curRes[0:len(curRes)-1]
    }
}

尾声，可以在循环体for中加一个target<0直接continue的判断，减少一次递归调用。增加执行效率。