解法一：（動態規劃）①定義：dp[i]表示是否可以在nums找到元素之和為i，dp[sum/2+1] ②初始狀態：dp[0]=true;dp[i]=false ③狀態轉移方程：dp[i] = dp[i] || dp[i - num];

class Solution {public boolean canPartition(int[] nums) {// 定義：dp[i]表示是否可以在nums找到元素之和為i，dp[sum/2+1]// 初始狀態：dp[0]=true;dp[i]=false// 狀態轉移方程：dp[i] = dp[i] || dp[i - num];int n = nums.length;// 先計算總和int sum = 0;for (int num : nums) {sum += num;}// 計算每個子集的和應該為多少int target = sum / 2;// 預先判斷// 如果和不能被2整除，則不能分為兩個子集if (sum % 2 != 0) {return false;}// 由于nums只包含正整數，若任意一個數大于target則不能滿足for (int num : nums) {if (num > target){return false;}}// 動態規劃boolean[] dp = new boolean[target+1]; // dp[i]=true表示能在數組nums中找到子集和為idp[0] = true;for (int num : nums) {// 不需要，后面for循環：// 當i=num時，dp[num]=dp[num]||dp[num-num]=dp[num]||dp[0]=false||true=true// 而且會錯誤// 沒有避免一個數被多次取和沒有取！！！！// dp[num] = true;  // 給每個dp[num]賦值，num一定存在// 循環num，嘗試把num加進去，確保每個dp[i]只會用到一個num// 第二層的循環我們需要從大到小計算，因為如果我們從小到大更新 dp 值，那么在計算 dp[j] 值的時候，dp[j?nums[i]] 已經是被更新過的狀態，不再是上一行的 dp 值。for (int i=target; i >= num; i--) {dp[i] = dp[i] || dp[i - num];}if(dp[target]){// 已經有子集了，提前結束return true;}}return dp[target];}
}

注意：

• 循環num，嘗試把num加進去，確保每個dp[i]只會用到一個num
• 第二層的循環我們需要從大到小計算，因為如果我們從小到大更新 dp 值，那么在計算 dp[j] 值的時候，dp[j?nums[i]] 已經是被更新過的狀態，不再是上一行的 dp 值。
• num一定存在，不需要dp[num] = true; 給每個dp[num]賦值。后面for循環：當i=num時，dp[num]=dp[num]||dp[num-num]=dp[num]||dp[0]=false||true=true；而且會錯誤，沒有避免一個數被多次取和沒有取！！！！錯誤：