题意：

image.png

解题思路：

  1. 思路：
  2. 优化剪枝
  3. 1. sort($candidates);
  4. 2. 剪枝： if ($i != $start && $candidates[$i] == $candidates[$i - 1]) continue;

PHP代码实现：

  1. class Solution {
  3.     public $res = []; 
  4.     function combinationSum2($candidates, $target) {
  5.         sort($candidates);
  6.         $this->dfs([], $candidates, $target, 0);
  7.         return $this->res;
  8.     }
  10.     function dfs($array, $candidates, $target, $start) {
  11.         if ($target < 0) return;
  12.         if ($target == 0) {
  13.             array_push($this->res, $array);
  14.             return;
  15.         }
  16.         for ($i = $start; $i < count($candidates); $i++) {
  17.             if ($i != $start && $candidates[$i] == $candidates[$i - 1]) continue;
  18.             array_push($array, $candidates[$i]);
  20.             // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
  21.             $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);
  22.             array_pop($array);
  23.         }
  24.     }
  25. }

GO代码实现：

  1. var res [][]int
  2. func combinationSum2(candidates []int, target int) [][]int {
  3.     res = make([][]int, 0)
  4.     sort.Ints(candidates)
  5.     dfs(candidates, []int{}, target, 0)
  6.     return res
  7. }
  9. func dfs(candidates, temp []int, target, start int) {
  10.     if target < 0 { return }
  11.     if target == 0 {
  12.         res = append(res, append([]int{}, temp...))
  13.         return
  14.     }
  15.     for i := start; i < len(candidates); i ++ {
  16.         if i > start  && candidates[i] == candidates[i - 1] {
  17.             continue
  18.         }
  19.         temp = append(temp, candidates[i])
  20.         dfs(candidates, temp, target - candidates[i], i + 1)
  21.         temp = temp[:len(temp)-1]
  22.     }
  23. }