### 题目描述补充 **题目：目标和** 给定一个非负整数数组 `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 示例代码 ```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 示例代码 ```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 示例代码 ```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]; } ``` 以上三种语言的实现都遵循了相同的逻辑，即使用动态规划来解决这个问题。希望这些示例对你有所帮助，并欢迎访问码小课网站获取更多相关内容！