题目描述：给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

注意：解集不能包含重复的组合。。

示例1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例2:

1
2
3
4
5
6
7

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

题解方法一：回溯+剪枝

算法思路
参考第39题

代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function combinationSum2(candidates, target) {
  function backtrack(state, target, choices, start, res) {
    // 子集和等于 target 时，记录解
    if (target === 0) {
      res.push([...state]);
      return;
    }
    // 遍历所有选择
    // 剪枝二：从 start 开始遍历，避免生成重复子集
    for (let i = start; i < choices.length; i++) {
     // 剪枝一：若子集和超过 target ，则直接结束循环
     // 这是因为数组已排序，后边元素更大，子集和一定超过 target
      if (target - choices[i] < 0) {
        break;
      }
      if (i > start && choices[i] == choices[i - 1]){
        continue
      }
                    
      // 尝试：做出选择，更新 target, start
      state.push(choices[i]);
      //  # 进行下一轮选择
      backtrack(state, target - choices[i], choices, i+1, res);
      state.pop();
    }
  }
  const state = []; // 状态（子集）
  candidates.sort((a, b) => a - b); // 对 candidates 进行排序
  const start = 0; // 遍历起始点
  const res = []; // 结果列表（子集列表）
  backtrack(state, target, candidates, start, res);
  return res;
}

总结：大功告成✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️✌️

参考链接: