分割等和子集

    1. class Solution {
    2.     public boolean canPartition(int[] nums) {
    3.         int len=nums.length;
    4.         if(len==1) return false;
    5.         int sum=0;
    6.         for(int i:nums) sum+=i;
    7.         if(sum%2!=0) return false;
    8.         sum=sum/2;
    9.         boolean[] dp=new boolean[sum+1];
    10.         //base
    11.         dp[0]=true;
    12.         for(int num:nums){
    13.             for(int i=sum;i>=num;i--){
    14.                 dp[i]=dp[i]||dp[i-num];
    15.             }
    16.         }
    17.         return dp[sum];
    18.     }
    19. }