leetcode39.组合总和

Problem: 39. 组合总和

思路

参考组合，组合是通过start=i+1避免选择重复元素，但本题是可以选择重复元素，所以start=i。没有规定是必须几个元素，核心思想和零钱兑换一样，但是硬币可以重复选。

Code

var mem []int
var res [][]int
func combinationSum(candidates []int, target int) [][]int {
    //核心思想，参考子集/组合/路径总和II/零钱兑换，我对这道题的理解是组合+零钱兑换
    mem=make([]int,0)
    res=make([][]int,0)

    dfs(0,target,candidates)
    return res
    
}

// start不要的话，会出现[2,2,3] [3,2,2] [2,3,2],用start来控制元素不会往前选，往前选肯定会出现此种重服组合
func dfs(start,amount int ,coins []int) {
    if amount==0{
        temp:=make([]int,len(mem))
        copy(temp,mem)
        res=append(res,temp)
        return 
    }
    if amount<0{
        return
    }
    

    for i:=start;i<len(coins);i++{
        mem=append(mem,coins[i])
        // start不用传i+1来避免重复,可以重复选择当前元素
        dfs(i,amount-coins[i],coins)
        mem=mem[:len(mem)-1]
    }
    return
}