sort之后 看有没有可以等于sum/2的

 

1 class Solution { 2     public boolean canPartition(int[] nums) { 3         if(nums.length == 0) return false; 4         int sum = 0; 5         for(int i = 0; i < nums.length; i++){ 6             sum += nums[i]; 7         } 8         Arrays.sort(nums); 9         if(nums[nums.length - 1] > sum/2) return false;10         if(sum % 2 != 0) return false;11         return dfs(nums, sum/2, nums.length-1);12         13     }14     15     public boolean dfs(int[] nums, int target, int start){16         if(target == 0) return true;17         if(target < 0) return false;18         for(int i = start; i >= 0; i--){19             if(dfs(nums, target - nums[i], i-1)){  //这便是i-1！！20                 return true;21             }22         }23         return false;24     }25     26 }