当前位置： 面试刷题>> 组合总和 (经典算法题500道)
### 题目描述补充
**题目：组合总和**
给定一个候选数字的集合（candidates）和一个目标数字（target），找出 candidates 中所有可以使数字和为 target 的组合。
**candidates** 中的每个数字在每个组合中只能使用一次。
**注意**：
- 解集不能包含重复的组合。
- 候选集合中的数字可以是不连续的，例如 [2, 3, 6, 7]。
- 候选集合中的数字可以包含重复的数字，例如 [2, 3, 3]。在这种情况下，重复的数字在最终解集中应被视为不同的元素，但组合中的重复数字（例如 [2,2]）不应被计入解集。
**示例 1**:
```
输入: candidates = [2,3,6,7], target = 7
输出: [[2,2,3],[7]]
解释:
2 和 3 可以组成 2+3=5，但这不是目标值 7，所以我们继续向后搜索。
2, 2, 3 的和为 7，是一个有效组合。
7 也是一个有效组合，因为它自身就等于 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, $tempList, &$result) {
if ($target == 0) {
$result[] = $tempList;
return;
}
if ($target < 0) {
return;
}
for ($i = $start; $i < count($candidates); $i++) {
// 跳过重复元素
if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
continue;
}
$tempList[] = $candidates[$i];
backtrack($candidates, $target - $candidates[$i], $i + 1, $tempList, $result);
array_pop($tempList);
}
}
// 示例用法
$candidates = [2, 3, 6, 7];
$target = 7;
$result = combinationSum2($candidates, $target);
print_r($result);
```
### Python 示例代码
```python
def combinationSum2(candidates, target):
def backtrack(start, path, target):
if target == 0:
result.append(path[:])
return
if target < 0:
return
for i in range(start, len(candidates)):
# 跳过重复元素
if i > start and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, target - candidates[i])
path.pop()
result = []
candidates.sort() # 先排序
backtrack(0, [], target)
return result
# 示例用法
candidates = [2, 3, 6, 7]
target = 7
result = combinationSum2(candidates, target)
print(result)
```
### JavaScript 示例代码
```javascript
function combinationSum2(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b); // 先排序
function backtrack(start, tempList, remaining) {
if (remaining === 0) {
result.push([...tempList]);
return;
}
if (remaining < 0) {
return;
}
for (let i = start; i < candidates.length; i++) {
// 跳过重复元素
if (i > start && candidates[i] === candidates[i - 1]) continue;
tempList.push(candidates[i]);
backtrack(i + 1, tempList, remaining - candidates[i]);
tempList.pop();
}
}
backtrack(0, [], target);
return result;
}
// 示例用法
const candidates = [2, 3, 6, 7];
const target = 7;
const result = combinationSum2(candidates, target);
console.log(result);
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例能帮助你更好地理解组合总和问题的解法。