题目链接
题意
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等
1 ≤ n u m s . l e n g t h ≤ 200 , 1 ≤ n u m s [ i ] ≤ 100 1 \le nums.length \le 200 ,1 \le nums[i] \le 100 1≤nums.length≤200,1≤nums[i]≤100
思路
转化成找出数组中一部分数相加等于数组总和的一半
n个元素，组成和为m=sum>>1是否可能
Code
class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;for(auto i:nums) sum+=i;if(sum&1) return 0;int m=sum>>1,n=nums.size();vector<int>a(n+1);for(int i=0;i<n;i++){a[i+1]=nums[i];}vector<vector<bool>>dp(n+1,vector<bool>(m+1));for(int i=0;i<=n;i++){dp[i][0]=1;}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j]=dp[i-1][j];if(a[i]==j) dp[i][j]=1;else if(a[i]<j) dp[i][j]=dp[i][j]|dp[i-1][j-a[i]];}}return dp[n][m];}
};
实现细节
对于dp[i][j]有三种情况 a[i]>j,==j,<j
