原题链接 (opens new window)

TIP

遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要 按某种顺序搜索。具体的做法是：每一次搜索的时候设置 下一轮搜索的起点

class Solution {

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

    function dfs($candidates, $target, $start, $path, &$result) {
        if ($target == 0) {
            $result[] = $path;
            return;
        }
        if ($target < 0) {
            return;
        }
        for ($i = $start, $iMax = count($candidates); $i < $iMax; $i++) {
            $path[] = $candidates[$i];
            //printf("start:%d,path:%s\n",$start,implode(" ",$path));
            $this->dfs($candidates, $target - $candidates[$i], $i, $path, $result);
            array_pop($path);
        }
    }
}

copy success