分割等和子集

class Solution {public:bool canPartition(vectorint nums) {int n nums.size();if (n 2)return false;int sum 0,mn0;//总和和最大值for (int i 0; i n; i){sum nums[i];if(nums[i]mn)mnnums[i];}if (sum % 2 1)//如果总和是奇数不行return false;int target sum / 2;if(mntarget)return false;//如果最大的数比和的一半都大也不行vectorvectorint dp(n 1, vectorint(target 1, 0));//枚举从0-n-1的数的组合能不能和为target dp[i][j]表示前i1个元素能不能组成和为jfor (int i 0; i n; i)dp[i][0]1;//和为零都可以达到dp[0][nums[0]]1;//数组第一个可以拿for (int i 1; i n; i) {int num nums[i];for (int j 1; j target; j) {//列举1-targetif (num j) {//如果这个数比枚举到的数大拿不了dp[i][j] dp[i - 1][j];} else {dp[i][j] dp[i-1][j - num] | dp[i - 1][j];//可以拿可以不拿}}}return dp[n - 1][target]!0;}};