Partition Equal Subset Sum

Approach: The key point to notice here is that we have to partition an array into two equal subsets sum so two equal subsets must have the sum equal to 'TOTALSUM'/2, where 'TOTALSUM' represents the sum of all elements in the given array, and also 'TOTALSUM' should be even as we cant partitioned an array into two equal if 'TOTALSUM' is odd,  So now the problem is to check if there is any subset in a given array with sum 'TOTALSUM'/2. And now this problem is similar to the classical 0/1 Knapsack Problem in which in the recursion call at any index, we have two choices whether to include that element in sum or exclude that element. Now if we choose the current number to add to the sum then recur for index 'I'+1  or If we don’t choose the current index element to sum then recur for index 'I'+1 and this way we check if there is a subset with sum 'TOTALSUM'/2 in the given array. 

 

Steps:

• Find the sum of all elements of the array that says 'TOTALSUM'.
• If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
• Define and call a helper function, 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX', 'SUBSETSUM') to check if there is subset with sum to 'TOTALSUM'/2, where 'ARR' is the given array and 'CURRENTINDEX' denotes the current index of given array and return 'CANPARTITIONUTIL'('ARR', 0, 'TOTALSUM' / 2)

Boolean 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX','SUBSETSUM')

• If 'CURRENTINDEX' reaches the end of the 'ARR' array or 'SUBSETSUM' < 0, return false.
• If 'SUBSETSUM' is equal to 0, return true, as we found a subset.
• Then we have two choices either to include or exclude element at index 'CURRENTINDEX' in 'SUBSETSUM':
  • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM' - 'ARR'['CURRENTINDEX'])
  • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM')
• If anyone of above choices return true, then return true.
• Else return false.

Approach: The previous approach uses recursion which has many overlapping subproblems. i.e recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems.

To reiterate memoization is when we store the results in a lookup 'ARR'ay('DP') of all previously solved subproblems and use the results from the 'DP' if we encounter the problem that has already been solved.

Since there are two states that are changing in the recursive function 'CANPARTITIONUTIL'() i.e 'CURRENTINDEX', and 'SUBSETSUM'  So we create a 2-dimensional array 'DP'[][] to store all the subproblems.

 

Steps:

• Find the sum of all elements of the array says 'TOTALSUM'.
• If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
• Create a 2-D array 'DP'[][] of length  'N', and 'TOTALSUM' / 2.
• Define and call a helper function, 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX', 'SUBSETSUM', 'DP') to check if there is subset with sum 'TOTALSUM'/2, where 'ARR' is the given array, 'CURRENTINDEX' denotes the current index of given array, and 'DP' represents the lookup 2-D array and return 'CANPARTITIONUTIL'('ARR', 0, 'TOTALSUM'/2,'DP').

Boolean 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX','SUBSETSUM','DP')

• If 'CURRENTINDEX' reaches the end of 'ARR' array or 'SUBSETSUM' < 0, return false.
• If 'SUBSETSUM' is equal to 0, return true as we found the subset.
• If we already solve the same subproblem for index 'CURRENTINDEX' and sum 'SUBSETSUM', return 'DP'['CURRENTINDEX']['SUBSETSUM'].
• Otherwise, we have two choices either to include or exclude element at index 'CURRENTINDEX':
  • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM' - 'ARR'['CURRENTINDEX'], 'DP').
  • 'CANPARTITIONUTIL'('ARR', 'CURRENTINDEX' + 1, 'SUBSETSUM', 'DP')
• Then store the results of both in 'DP'['CURRENTINDEX']['SUBSETSUM'], and return  'DP'['CURRENTINDEX']['SUBSETSUM'].

Approach:

• The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. Let us assume 'DP'['I']['J'] means whether the specific 'SUM' j can come from the first I numbers in an array. If we can pick such a series of numbers from 0-i whose 'SUM' is j, 'DP'['I']['J'] is true, otherwise, it is false.
• Essentially, we want to find if we can make all possible 'SUM's with every subset. This means 'DP'['I']['J'] will be ‘true’ if we can make 'SUM' j from the first I numbers.
• For the base case, we set 'DP'[0][0] to true since with 0 elements a subset-'SUM' of 0 is possible.
• Now, 'DP'['I']['J'] is true if 'DP'[i-1]['J'] is true As we skipped this element, and took the 'SUM' of the previous result or 'DP'['I'-1]['J' - element’s value] assuming this isn’t out of range(meaning that we added this value to our subset-'SUM' so we look at the 'SUM'-current element’s value).
• If 'DP'['N']['SUM'/2] is true that means we were able to find a 'SUM' of 'SUM'/2 out of 'N' elements which is what we want to check.

 

 

Steps:

• Find the 'SUM' of all elements of array say 'TOTALSUM'.
• If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
• Create a new auxiliary array 'DP' of length 'N' * 'TOTALSUM' / 2.
• Iterate the given array, now for each index 'I' we run a loop from 0 to 'TOTALSUM' / 2 then at each index 'J' we have two choices:
  • Exclude the number. In this case, we will see if we can get 'J' from the subset excluding this number: 'DP'[i-1]['J']
  • Include the number if its value is not more than 'J'. In this case, we will see if we can find a subset to get the remaining 'SUM': 'DP'['I' - 1]['J' - 'NUMS'['I']]
• If either of the two above choices is true then we can find a subset of numbers with 'SUM' 'J'.
• At last, return 'DP'['N']['TOTALSUM' / 2].

Approach: We see in a previous approach that we only need current index 'I' , and previous index 'I' - 1, and the rest of the indexes are a waste of space, So, we can achieve the same using a one-dimensional array as well.

 

Steps:

• Find the sum of all elements of the array says 'TOTALSUM'.
• If 'TOTALSUM' is not divisible by 2 return false, as array cant be partitioned into two equal subsets.
• Create a new auxiliary 1-D array 'DP' of length 'TOTALSUM'/2.
• Iterate the given array, now for each index 'I' we run a loop from 'TOTALSUM'/2 to 0 then at each index 'J' we check:
  • If 'J'- 'ARR'['I'-1]>=0 then 'DP'['J'] = 'DP'['J' - 'NUMS'['I' - 1]] or 'DP'['J']
• At last, return 'DP'['TOTALSUM'/ 2].