链接 (opens new window)

class Solution {

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

    function dfs($candidates, $target, $start, $used, $path, &$result) {
        if ($target == 0) {
            $result[] = $path;
            return;
        }
        if ($target < 0) {
            return;
        }
				//通过指定遍历起点 使得解集不包含重复的组合
        for ($i = $start, $iMax = count($candidates); $i < $iMax; $i++) {
				    //这个地方的$used 用来判断是否是第二次使用相同元素 
            if (!$used[$i]) {
                if ($i > 0 && $candidates[$i] == $candidates[$i - 1] && !$used[$i - 1]) {
                    continue;
                }
								// 不使用 used 也可以用$i > $start 同层级相同元素非第一个分支剪掉
                // if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
                //   continue;
                //}

                $used[$i] = 1;
                $path[] = $candidates[$i];
                $this->dfs($candidates, $target - $candidates[$i], $i + 1, $used, $path, $result);
                array_pop($path);
                $used[$i] = 0;
            }
        }
    }
		
		    function dfs2($candidates, $target, $start, $used, $path, &$result) {
        if ($target == 0) {
            $result[] = $path;
            return;
        }
        if ($target < 0) {
            return;
        }
        for ($i = $start, $iMax = count($candidates); $i < $iMax; $i++) {
            //if (!$used[$i]) {
                //if ($i > 0 && $candidates[$i] == $candidates[$i - 1] && !$used[$i - 1]) {
                //    continue;
                //}
                if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
                    continue;
                }
                $used[$i] = 1;
                $path[] = $candidates[$i];
                $this->dfs2($candidates, $target - $candidates[$i], $i + 1, $used, $path, $result);
                array_pop($path);
                $used[$i] = 0;
            //}
        }
    }

}

copy success