题目描述补充

题目：组合总和

给定一个候选数字的集合（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 示例代码

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 示例代码

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 示例代码

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);

码小课网站中有更多相关内容分享给大家学习，希望这些示例能帮助你更好地理解组合总和问题的解法。