Leetcode — 416. Partition Equal Subset Sum

The link to the problem: https://leetcode.com/problems/partition-equal-subset-sum/

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Example: 
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Thoughts:

My first thought will be, we need to find two sets that contain half of the sum of the whole array. What’s more, we actually only need to find 1 set that meets the condition. Because if one set contains the sum of x, then the sum of the remaining numbers will also be x. The problem sounds easier right now, right? We can even just return false if we found the total sum of the whole array is not divisible by 2.

After checking the edge cases, we can just convert our problem into — return true or false if we can form a set contains the sum of x.

Since all the numbers are in the range of [1, 100], I’m hoping we can use the idea of backtracking to solve the problem. We can just pick a number and try to see if we can pick several numbers in the rest of the array to form the target sum. If not, we will drop the number and try another one.

Let’s see how we convert this idea into code.

Code Logic:

Before we start to do backtracking code, we need to first prepare what we need — the sum of the target set and a map array that represents the occurrence of the number in the given nums array. (i.e., we will know number i appears map[i] times in the given array.)

Then our first step is to make an assumption that the biggest number of the given array is in our current set. The reason why we make this assumption is that we want to shorten the time to find the target sum. Also, this biggest number MUST BE in one of the partitioned sets. Hence, we can just assume we are going to find the set that contains this number.

We will have a helper method that returns if we can use the current remaining numbers to form a set that contains the target sum. We will also start to pick our numbers from the biggest number that we can pick so that we can speed up some time to find the target sum. If we failed to pick the number, then we will just redo and pick the next smaller number.

⚠️About the biggest number that we can pick — it means that we will pick a number that is less than and equal to the target sum AND the biggest number we might have in the array (i.e., 100).

public boolean canPartition(int[] nums) {
        int sum = 0;
        int[] map = new int[101];
        int max = 0;
        for(int num: nums)
        {
            sum += num;
            map[num]++;
            max = Math.max(max, num);
        }
        if(sum%2==1 || nums.length==1)
            return false;
        
        sum/=2;
        map[max]--;
        return helper(map, sum-max);
    }
    public boolean helper(int[] map, int target){
        if(target<0)
            return false;
        if(target==0) 
            return true;
        int max = Math.min(100,target);
        for(int i=max;i>=0;i--)
        {
            if(map[i]==0)
                continue;
            map[i]--; //choose number i
            if(helper(map, target-i))
                return true;
            map[i]++; //redo
        }
        return false;
    }

The above code will be Time Limit Exceeded in most of the test cases on Leetcode. The reason is that we keep checking if we can form the same target sum again and again. To solve this problem, we can just add a set that record all the target sums that we failed to form.

Below is the 2ms code that beats 98% —

public boolean canPartition(int[] nums) {
        int sum = 0;
        int[] map = new int[101];
        int max = 0;
        for(int num: nums)
        {
            sum += num;
            map[num]++;
            max = Math.max(max, num);
        }
        if(sum%2==1 || nums.length==1)
            return false;
        
        sum/=2;
        map[max]--;
        return helper(map, sum-max, new HashSet<>());
    }
    public boolean helper(int[] map, int target, Set<Integer> failed){
        if(target<0 || failed.contains(target))
            return false;
        if(target==0)
            return true;
        
        int max = Math.min(100,target);
        for(int i=max;i>=0;i--)
        {
            if(map[i]==0)
                continue;
            map[i]--;
            if(helper(map, target-i, failed))
                return true;
            map[i]++;
        }
        failed.add(target);
        return false;
    }