当前位置: 面试刷题>> 目标和 (经典算法题500道)


题目描述补充

题目:目标和

给定一个非负整数数组 nums 和一个整数 target,数组 nums 可以包含重复元素。请你判断是否存在一个子集,使得子集元素之和等于 target。请注意,数组中的元素可以重复使用。

示例 1:

输入: nums = [1, 1, 1, 1, 1], target = 3
输出: True
解释: 数组 [1, 1, 1] 的和等于 3。

示例 2:

输入: nums = [1, 1, 1, 1, 1], target = 4
输出: False

解题思路

这个问题可以使用动态规划(Dynamic Programming)或者回溯法(Backtracking)来解决。由于题目中允许元素重复使用,且我们关心的是是否存在子集的和等于 target,动态规划的方法在这里更为合适。

我们可以将问题转化为“背包问题”的一个变种,即考虑每个元素可以被选择多次,目标是填满一个容量为 target 的背包。

动态规划解法(PHP、Python、JavaScript)

PHP 示例代码

function canPartition($nums, $target) {
    $sum = array_sum($nums);
    if ($sum < $target) return false; // 总和小于目标值,直接返回false
    if ($sum % 2 != $target % 2) return false; // 奇偶性不一致,无法构成目标和
    
    $target = $sum - $target; // 转化为求是否存在和为sum/2的子集
    $dp = array_fill(0, $target + 1, false);
    $dp[0] = true; // 初始化,和为0总是可以构成
    
    foreach ($nums as $num) {
        for ($i = $target; $i >= $num; $i--) {
            $dp[$i] = $dp[$i] || $dp[$i - $num];
        }
    }
    
    return $dp[$target];
}

Python 示例代码

def canPartition(nums, target):
    total_sum = sum(nums)
    if total_sum < target:
        return False
    if total_sum % 2 != target % 2:
        return False
    
    target = (total_sum - target) // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    return dp[target]

JavaScript 示例代码

function canPartition(nums, target) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum < target) return false;
    if (sum % 2 !== target % 2) return false;
    
    target = Math.floor((sum - target) / 2);
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    
    for (const num of nums) {
        for (let i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    
    return dp[target];
}

以上三种语言的实现都遵循了相同的逻辑,即使用动态规划来解决这个问题。希望这些示例对你有所帮助,并欢迎访问码小课网站获取更多相关内容!

推荐面试题