[数据结构与算法]经典动态规划：背包问题！！（结合LC416官方视频解释！！）

题目：

给你一个?只包含正整数?的?非空?数组?nums?。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

题解：

给定一个只包含正整数的非空数组 nums[0]，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。因此这个问题可以转换成「0?1 背包问题」。这道题与传统的0?1 背包问题」的区别在于，传统的0?1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的0?1 背包问题」，使用动态规划求解。

class Solution {
    public boolean canPartition(int[] nums) {
      int len=nums.length;

      int sum=0;
      for(int num:nums){
          sum+=num;
      }
      if((sum&1)==1){
          return false;
      }

      int target=sum/2;
      boolean[]dp=new boolean[target+1];
      dp[0]=true;
      if(nums[0]<=target){
          dp[nums[0]]=true;
      }

      for(int i=1;i<len;i++){
          for(int j=target;j>=0&&nums[i]<=j;j--){
              dp[j]=dp[j]||dp[j-nums[i]];
          }
          if(dp[target]){
              return true;
          }

      }
      return dp[target];
    }
}