题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
解题
方法一：回溯（超时）
因为两个子集分别的和是要一样的，因此每个子集的和是 总和的一半，必须要为整数。
传入的参数需要有target,sum,startIndex
由于遇到sum==target要立刻返回，所以backtarcing还有返回值bool
class Solution { public: bool backtracing(vector<int>& nums,int target,int sum,int startIndex){ if(sum==target){ return true; }else if(sum>target) return false; for(int i=startIndex;i<nums.size();i++){ sum+=nums[i]; if(backtracing(nums,target,sum,i+1)) return true; sum-=nums[i]; } return false; } bool canPartition(vector<int>& nums) { sort(nums.begin(),nums.end()); float target=(float)accumulate(nums.begin(),nums.end(),0)/2; if(target!=(int)target) return false; return backtracing(nums,target,0,0); } };
方法二：动态规划
可以理解成背包问题
背包容量为sum/2
每个物品的重量为数值nums[i]
每个物品的价值为数值nums[i]
只要背包能装满，就认为可以分割成等和子集
class Solution { public: bool canPartition(vector<int>& nums) { int sum=accumulate(nums.begin(),nums.end(),0); if(sum%2==1) return false; int target=sum/2; vector<int> dp(target+1); for(int i=0;i<nums.size();i++){ for(int j=target;j>=nums[i];j--){ dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]); } } if(dp[target]==target) return true; else return false; } };
java
class Solution { public boolean canPartition(int[] nums) { int sum=0; for(int num:nums) sum+=num; if(sum%2!=0) return false; int target=sum/2; int[] dp=new int[target+1]; for(int i=0;i<nums.length;i++){ for(int j=target;j>=nums[i];j--){ dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]); } } return dp[target]==target; } }
