题目描述

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

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

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

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

在这三个示例中，我们都使用了回溯算法，并进行了排序和剪枝来优化性能。希望这些示例能帮助你理解并解决这个问题。