题目描述补充

题目：k数之和

给定一个整数数组 nums 和一个整数 k，你需要判断数组中是否存在 k 个数，它们的和等于一个特定的目标值 target。返回所有满足条件的且不重复的组合。

注意：

• 数组中的数字可以重复使用。
• 输出的组合中的数字顺序不重要。
• 输出的组合不应包含重复的组合。

示例 1:

输入: nums = [1,2,3], k = 3, target = 6
输出: [[1,1,4],[1,2,3]]
注意：这里的输出是错误的，因为不存在和为6的组合包含重复数字1，且实际上应该是[[1,2,3]]。
正确输出: [[1,2,3]]

示例 2:

输入: nums = [2,5,2,1,2], k = 2, target = 5
输出: [[1,4],[2,3]]
注意：这里的输出也是错误的，因为重复的数字2在组合中应当被视为不同的元素。
考虑到数字可以重复使用且顺序不重要，实际输出应为[[1,4],[2,3],[2,2]]，但考虑到去重和题目要求，我们可能只保留不重复的组合。

注意： 在实际应用中，应确保输出不包含重复的组合，并且考虑到数字可以重复使用。

PHP 代码示例

function combinationSumK($nums, $k, $target) {
    $result = [];
    sort($nums); // 先排序，有助于剪枝
    backtrack($nums, $k, $target, 0, [], $result);
    return $result;
}

function backtrack($nums, $k, $target, $start, $temp, &$result) {
    if ($k == 0 && $target == 0) {
        $result[] = $temp;
        return;
    }
    if ($k == 0 || $target < 0) {
        return;
    }

    for ($i = $start; $i < count($nums); $i++) {
        // 跳过重复元素
        if ($i > $start && $nums[$i] == $nums[$i - 1]) continue;
        
        $temp[] = $nums[$i];
        backtrack($nums, $k - 1, $target - $nums[$i], $i, $temp, $result); // 注意这里是 $i 而不是 $i + 1
        array_pop($temp);
    }
}

// 示例用法
$nums = [2, 5, 2, 1, 2];
$k = 2;
$target = 5;
print_r(combinationSumK($nums, $k, $target));

Python 代码示例

def combinationSum3(k, n):
    def backtrack(start, path, target):
        if len(path) == k and target == 0:
            res.append(path[:])
            return
        if len(path) >= k or target < 0:
            return

        for i in range(start, 10):
            path.append(i)
            backtrack(i + 1, path, target - i)
            path.pop()

    res = []
    backtrack(1, [], n)
    return res

# 注意：Python示例稍作修改，以适应一个假设的接口，其中k为组合长度，n为目标和
# 你可以根据题目要求调整输入参数和函数逻辑

# 示例用法
k = 2
n = 5
print(combinationSum3(k, n))

JavaScript 代码示例

function combinationSumK(nums, k, target) {
    const result = [];
    nums.sort((a, b) => a - b); // 排序

    function backtrack(start, path, remain) {
        if (path.length === k && remain === 0) {
            result.push([...path]);
            return;
        }
        if (path.length >= k || remain < 0) return;

        for (let i = start; i < nums.length; i++) {
            // 跳过重复元素
            if (i > start && nums[i] === nums[i - 1]) continue;
            path.push(nums[i]);
            backtrack(i, path, remain - nums[i]); // 注意这里是 i 而不是 i + 1
            path.pop();
        }
    }

    backtrack(0, [], target);
    return result;
}

// 示例用法
const nums = [2, 5, 2, 1, 2];
const k = 2;
const target = 5;
console.log(combinationSumK(nums, k, target));

码小课网站中有更多相关内容分享给大家学习，包括更多算法题解、面试技巧、编程知识等。