題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/partition-equal-subset-sum
給定一個只包含正整數(shù)的非空數(shù)組捺萌。是否可以將這個數(shù)組分割成兩個子集医寿，使得兩個子集的元素和相等毒返。
注意:
每個數(shù)組中的元素不會超過 100
數(shù)組的大小不會超過 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組不能分割成兩個元素和相等的子集.
遞歸解法（將問題轉換為在數(shù)組中能否找出累加和為一半總值）：
class Solution {
public boolean canPartition(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum%2 == 0){
//取一半
sum /= 2;
//在數(shù)組中找出累加和等于一半值的劝萤，找不到就返回false
return valid(nums,nums.length-1,sum);
}
return false;
}
private boolean valid(int[] nums,int len,int target){
if(target == 0)
return true;
for(int i = len;i>=0;i--){
if(nums[len] <= target){
if(valid(nums,i-1,target-nums[i])){
return true;
}
}
}
return false;
}
}
