Java easy solution with explanation


  • 0
    S
    public boolean canPartition(int[] nums) {
            int sum = 0;
            for(int i : nums){
                sum += i;
            }
            if (sum % 2 == 1) return false;
            Arrays.sort(nums);
            return helper(nums, sum / 2, nums.length - 1);
        }
        private boolean helper(int[] nums, int sum, int end){
            if (sum == 0 && end >= 0){
                return true;
            }
            for(int i = end; i >= 0; i--){
                if (nums[i] > sum) break;
                sum -= nums[i];
                boolean res = helper(nums, sum, i - 1);
                if (res){
                    return true;
                }
                sum += nums[i];
            }
            return false;
        }
    

    If the sum is odd, return false. If not, we need to know if we can find a subset, which have a sum of half of original sum. Remember there is a DFS problem, give all combinations that sum to a target? The same idea. Just don't need all solutions.

    One thing to mention is that, to avoid time limit, we need to loop the nums array from end to head, so that for the big numbers, we can directly break, when the input is like this:
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.