acqcc

416. Partition Equal Subset Sum

Aug 04, 20223 min read

Problem Statement

Partition Equal Subset Sum - LeetCode Subset Sum Problem : Find if there is a subset in array whose sum equals target

Pattern: Pattern DP Subset Sum

Approach 1

Brute Force

public boolean canPartition (int[] nums){
	return f(nums, nums.length-1, 0, 0);
}
boolean f(int[] nums, int n, int sum1, int sum2) {
	if(n < 0) return sum1==sum2;		
	return f(nums, n-1, sum1+nums[n], sum2)
		|| f(nums, n-1, sum1, sum2+nums[n]);
}

TC : SC :

Memoised

int[][] cache;
public boolean canPartition (int[] nums){
	cache = new int[nums.length][20000+1];
	for(int[] row : cache) Arrays.fill(row, -1);
	return f(nums, nums.length-1, 0, 0);
}
 
boolean f(int[] nums, int n, int sum1, int sum2) {
	if(n < 0) return sum1==sum2;
	if(cache[n][sum1] != -1){ return cache[n][sum1] == 1;}
	
	boolean found = f(nums, n-1, sum1+nums[n], sum2)
				 || f(nums, n-1, sum1, sum2+nums[n]);
	cache[n][sum1] = found ? 1 : 0;
	return found;
}

TC : n*sum

Approach 2

Optimised Brute Force

public boolean canPartition(int[] nums) {  
   int sum = 0;  
   for (int num : nums) sum += num;  
   if(sum%2 != 0) return false;  
   return f(nums, nums.length - 1, sum/2);  
}  
  
boolean f(int[] nums, int n, int target) {  
   if (n < 0) return target == 0;  
   if(target == 0) return true;  
   if(nums[n] <= target) 
	   return f(nums, n - 1, target-nums[n]) || f(nums, n - 1, target);
   return f(nums, n - 1, target);
}
  • 2 partitions can be equal only if the sum is even
  • so simply track if a single sum/2 can be reached, by any subset in the array

Optimised Memoised

Boolean[][] cache;
 
public boolean canPartition(int[] nums) {
	int sum = 0;
	for (int num : nums) sum += num;
 
	if(sum%2 != 0) return false;
	cache = new Boolean[nums.length][sum/2+1];
 
	return f(nums, nums.length - 1, sum/2);
}
 
boolean f(int[] nums, int n, int target) {
	if (n < 0) return target == 0;
	if(target == 0) return true;
 
	if(cache[n][target] != null) return cache[n][target];
 
	if(nums[n] <= target) 
		cache[n][target] = f(nums, n - 1, target-nums[n]) || f(nums, n - 1, target);
	else 
		cache[n][target] = f(nums, n - 1, target);
	
	return cache[n][target];
}

TC : n*sum/2

Iterative

public boolean canPartition(int[] nums) {
	int k = 0, n = nums.length;
	for (int num : nums) k += num;
	if (k % 2 != 0) return false;
	k/=2;
 
	// init dp
	boolean dp[][] = new boolean[n + 1][k + 1];
	for (int j=0, i = 1; i < n+1; i++) dp[i][j] = true;
	// for (int j=1, i = 0; j < k+1; j++) dp[i][j] = false; // redundant
 
	for (int i = 1; i < n+1; i++)
		for (int j = 1; j < k + 1; j++)
			if(nums[i-1] <= j)
				dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j];
			else dp[i][j] = dp[i-1][j];
	return dp[n][k];
}

TC :

Notes

if(nums[i-1] <= j)
	dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j]; // 👈 what does this mean
else dp[i][j] = dp[i-1][j];
dp[ith item][sum equalling j] is true if either of the following is true	
- dp[i-1th item][sum = j  value of the ith item] is true
- dp[i-1th item][sum = j] is true

Graph

Backlinks