39. 组合总和

题意：

解题思路：

思路：
优化剪枝
1. sort($candidates);
2. if ($candidates[$i] > $target) break;
3. 传入 i 而不是 i+1 是为了数字能重复使用;

PHP代码实现：

class Solution {
    public $res = [];
    function combinationSum($candidates, $target) {
        sort($candidates);
        $this->dfs([], $candidates, $target, 0);
        return $this->res;
    }
    function dfs($array, $candidates, $target, $start) {
        if ($target < 0) return;
        if ($target == 0) {
            array_push($this->res, $array);
            return;
        }
        for ($i = $start; $i < count($candidates); $i++) {
            if ($candidates[$i] > $target) break;
            array_push($array, $candidates[$i]);
            $this->dfs($array, $candidates, $target - $candidates[$i], $i);
            array_pop($array);
        }
    }
}

GO代码实现：

var res [][]int
func combinationSum(candidates []int, target int) [][]int {
    res = make([][]int, 0)
    dfs(candidates, []int{}, target, 0)
    return res
}
func dfs(candidates, temp []int, target, start int) {
    if target < 0 { return }
    if target == 0 {
        res = append(res, append([]int{}, temp...))
        return
    }
    for i := start; i < len(candidates); i ++ {
        temp = append(temp, candidates[i])
        // 这里传入 i 而不是 i+1 是为了数字能重复使用
        // i+1 数字就无法重复使用
        dfs(candidates, temp, target - candidates[i], i)
        temp = temp[:len(temp)-1]
    }
}