Partition Problem


We are given an array of n integers. We have to divide the array elements into two subsets such that sum of the elements in both the subsets are equal. Union of two subsets will contain all the array elements.


Naive Approach

· We will check for every possible partition.

· For that we will have to select all possible subsets and check whether the sum of the elements of that subset and sum of the remaining elements are equal or not.

· For generating the subset at each index we will have two possibilities either to include that element or not.

Time Complexity :

· Since at each step we have 2 possiblities and we have n integers.

  • So, there will be 2n subsets and hence the time complexity will be O(2n).

· We can use a similar approach to optimize our solution by using memoization.

Efficient Solution

· First step is to think of some states which we can relate to solve bigger problems.

· When we are at a certain index we only need the integers which we have taken till that index.

· But since we are interested only in sum of them, the integer values are of no use to us. We only need the sum of them.

· So, we can think of dp[i][j] , where i is the index number and j is the sum of elements taken till that index.

· If the value dp[i][j] is 0 then our partition is not correct. So even if any one dp[i][j] is 1 then we can partition according to the given question.

· Now we have to relate them so that we can solve it for a bigger problem.

· Since, we have only two possibilities at each index as discussed earlier, we will consider both cases one by one.

  • I am at ith index and I have taken j sum till now, and if I take the ith integer, then our state will be shifted to dp[i+1][j+a[i]]. Similarly if I do not take ith integer, then our state will be shifted to dp[i+1][j].

· If a partition is giving the desired result in any of the two possibilities then the given condition will be satisfied.

· So, we should use OR operator between the two possibilities.

· dp[i][j] = dp[i+1][j+a[i]] || dp[i+1][j]


Important Case :

· When sum of all the given integers is odd, then there is no way to partition the array into two parts such that we will have equal sum in both the subsets.

· This is because sum of two same integers will always give an even number.

· In that case we can directly return 0.

Base Cases :

· If i == n, then we should return 0 as we have not yet find the correct partition and we have no more integers left.

· If sum == tot/2, then we should return 1 as we have found a correct partition. Here, tot refers to the sum of all integers of the array.


Code :

Note : Here, dp is initialized with -1, a is the array of given integers, tot is the sum of all integers of the array, index refers to the index in which we are currently at and n is the number of integers.


Practice Problems :



Happy Coding 😊

By Programmers Army

Contributed by Shubham Kumar