1. 题干说明

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

2. 解法

<?php
class Solution {
    private $ret = [];
    /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    public function combinationSum($candidates, $target) {
        $this->dp($candidates, $target, [], 0);
        return array_values($this->ret);
    }
    private function dp($candidates, $target, $elements = [], $start = 0) {
        if ($target < 0) {
            return;
        }
        if ($target == 0) {
            sort($elements);
            $inRet = implode(',', $elements);
            $this->ret[$inRet] = $inRet;
            return;
        }
        for ($i = $start + 1; $i < count($candidates); $i++) {
            $value = $candidates[$i];

            array_push($elements, $value);
            $this->dp($candidates, ($target - $value), $elements, $i);
            array_pop($elements);
        }
    }
}
$candidates = [10,1,2,7,6,1,5];
$target = 8;
$cls = new Solution();
$r = $cls->combinationSum($candidates, $target);
print_r($r);