当前位置： 面试刷题>> 组合总和(经典算法150题)
### 题目描述
给定一个候选数字的集合（candidates）和一个目标数字（target），找出 candidates 中所有可以使数字和为 target 的组合。
**candidates** 中的每个数字在每个组合中只能使用一次。
**注意**：
- 解集不能包含重复的组合。
- 所有数字（包括 target）都是正整数。
- 解集应当按字典序排列。
### 示例
**示例 1**:
```
输入: candidates = [2,3,6,7], target = 7
输出: [[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选，[2,3]。
2, 2, 和 3 可以形成一组候选，[2,2,3]。
7 可以单独形成一组。
```
**示例 2**:
```
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
```
**示例 3**:
```
输入: candidates = [2], target = 1
输出: []
```
### 解题思路
为了解决这个问题，我们可以使用回溯算法。回溯算法通过递归地尝试构建解，并在构建过程中撤销上一步的尝试（即回溯）来找到所有可能的解。
### PHP 示例代码
```php
function combinationSum2($candidates, $target) {
$result = [];
sort($candidates); // 排序确保按字典序排列
backtrack($candidates, $target, 0, [], $result);
return $result;
}
function backtrack($candidates, $target, $start, $combination, &$result) {
if ($target === 0) {
$result[] = $combination;
return;
}
for ($i = $start; $i < count($candidates); $i++) {
// 避免使用重复的数字
if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
continue;
}
if ($candidates[$i] > $target) {
break; // 剪枝
}
// 选择当前数字
$combination[] = $candidates[$i];
// 递归调用，注意i+1，表示当前数字只能用一次
backtrack($candidates, $target - $candidates[$i], $i + 1, $combination, $result);
// 撤销选择
array_pop($combination);
}
}
```
### Python 示例代码
```python
def combinationSum2(candidates, target):
def backtrack(start, path, target):
if target == 0:
result.append(path)
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if candidates[i] > target:
break
backtrack(i + 1, path + [candidates[i]], target - candidates[i])
candidates.sort()
result = []
backtrack(0, [], target)
return result
```
### JavaScript 示例代码
```javascript
function combinationSum2(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b); // 排序
function backtrack(start, path, remaining) {
if (remaining === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] === candidates[i - 1]) continue; // 跳过重复
if (candidates[i] > remaining) break; // 剪枝
path.push(candidates[i]);
backtrack(i + 1, path, remaining - candidates[i]);
path.pop();
}
}
backtrack(0, [], target);
return result;
}
```
在这三个示例中，我们都使用了回溯算法，并进行了排序和剪枝来优化性能。希望这些示例能帮助你理解并解决这个问题。