1. 题干说明

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。

• 解集不能包含重复的组合。

  示例 1：
  输入：candidates = [2,3,6,7], target = 7,
  所求解集为：
  [
  [7],
  [2,2,3]
  ]

  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 $this->ret;
    }
  
    private function dp($candidates, $target, $elements = [], $start = 0) {
        if ($target < 0) {
            return;
        }
        if ($target == 0) {
            $this->ret[] = implode(',', $elements);
            return;
        }
        // 递归是从左到右执行的，因此相对于右边的数字，已经被左边的递归运行过了，所以不需要再从最左边的数进行迭代
        for ($i = $start; $i < count($candidates); $i++) {
            $value = $candidates[$i];
            array_push($elements, $value);
            $this->dp($candidates, ($target - $value), $elements, $i);
            array_pop($elements);
        }
    }
  }
  $candidates = [2,3,6,7];
  $target = 7;
  $cls = new Solution();
  $r = $cls->combinationSum($candidates, $target);
  print_r($r);