Combination Sum

https://leetcode.com/problems/combination-sum/
给定一个数组，找出内部所有的相加等于该数字的组合

 /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        $out = [];
        $res = [];
        $this->combinationHelper($candidates, $target, 0, $out, $res);
        return $res;
    }

    /**
     * combinationHelper
     * @param $nums
     * @param $target
     * @param $start
     * @param $out
     * @param $res
     * @return void
     */
    function combinationHelper($nums, $target, $start, &$out, &$res) {
        if ($target < 0) {
            return;
        }

        if ($target == 0) {
            $res[] = $out;
            return;
        }

        for ($i = $start; $i < count($nums); $i++) {
            $out[] = $nums[$i];
            $this->combinationHelper($nums,$target - $nums[$i],$i,$out,$res);
            array_pop($out);
        }
    }

https://leetcode.com/problems/combination-sum-ii/
升级版的combination Sum， 要求每个数字不能重复出现，稍微改一下就行，没太大区别

 function combinationSum2($nums, $target) {
        $out     = [];
        $res     = [];
        $visited = [];
        sort($nums);
        $this->combinationHelper2($nums, $target, 0, $out, $res, $visited);
        return $res;
    }

    function combinationHelper2($nums, $target, $start, &$out, &$res, &$visited) {
        if ($target < 0) {
            return;
        }

        if ($target == 0) {
            $res[] = $out;
            return;
        }

        for ($i = $start; $i < count($nums); $i++) {
            if($i > $start && $nums[$i] == $nums[$i-1]){
                continue;
            }
            $out[]       = $nums[$i];
            $visited[$i] = 1;
            $this->combinationHelper2($nums, $target - $nums[$i], $i + 1, $out, $res,$visited);
            array_pop($out);
        }
    }

https://leetcode.com/problems/combination-sum-iii/
升级版的combination sum, 要求特定K个数字相加后等于N

 public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> out = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int[] visited = new int[10];
        combineHepler3(k, n, visited, out, res);
        return res;
    }

    public void combineHepler3(int k, int n, int[] visited, List<Integer> out, List<List<Integer>> res) {
        if (n == 0 && k == 0) {
            res.add(new ArrayList<Integer>(out));
            return;
        }

        if (n <= 0 || k <= 0) {
            return;
        }

        int tmp = out.size() > 0 ? out.get(out.size() - 1) : 1;
        for (int i = tmp; i <= 9; i++) {
            if (visited[i] == 1 || i > n) {
                continue;
            }

            visited[i] = 1;
            out.add(i);
            this.combineHepler3(k - 1, n - i, visited, out, res);
            out.remove(out.size() - 1);
            visited[i] = 0;
        }
    }