Equal Subset Sum Partition of Array or List in Python

In this article, we will see if the given array/list can be partitioned into two subsets such that both have equal sums in Python.

It means we will do a partition in an array or list such that the sum of elements in each subset will be equal. This question is asked in many top Tech company’s interview/coding rounds.

So now let’s see the Problem Statement for this problem:

Equal Sum Partition of an Array or a List in Python

A non-empty array/list (A) is given having only positive numbers, we have to find if the given array can be partitioned into two subsets such that both have the same sums no matter if the size of subsets is equal or not.

EXAMPLE:

INPUT:    A = [1 , 5 , 11 , 5]

OUTPUT:  TRUE

Explanation:

The two sebsets [1 , 5 , 5] and [11] both have sum equal to 11 i.e (1 + 5 + 5 = 11) and (11 = 11)

So Output will be TRUE.

So now coming on to the concept behind this question which will help us in solving this question:

If we will notice then it is obvious in actual we are partitioning the sum of elements of the given array in two parts (number of elements does not matter in subsets).

i.e  [1 , 5 , 11 , 5] , sum of each element of array/list will be 22.

Now we will look for subsets that have the sum equal to (sum of each element of the array)/2 i.e, (22/2 = 11). Because if anyone subsets have the sum equal to half of the sum of the array’s element sum then it is obvious that another subset is also present which have the same sum (half of the sum of the array’s elements).

We can only do this partitioning if the sum of elements of a given array/list is even. In case of odd, it is impossible.

i.e [1 , 5 , 11 ,4] , the sum of each element of given array/list is 21 . In this case, we can not make partitioning such that both subsets have equal sum ..NOT POSSIBLE.

So, In the case of ODD sum, FALSE will be output.

This problem is based on subsets sum, so we can use Dynamic Programming. We can solve this problem using the subproblem concept, which means we can use Dynamic Programming. Since it is the subset sum problem type question, so think about the concept which we use in Knapsack Problem !!……..

So we will solve this problem for its sub-problem and in this way, we will achieve output for our real input, which means using the output of sub-problems we will get our output for our input. This is the concept which we use in the case of Dynamic Programming.

So now start implementing the code for this problem:

Code for the problem statement:

def part(LIST):
    sum=0
    i=0;
    for i in range(i,len(LIST)):
        sum = sum+LIST[i]        # sum of all elements of list 
    if(sum%2!=0):
        return("FALSE")          # if odd not possible to make partitioning
    elif(sum%2 == 0):
        k = int(sum/2)           # subset having sum = k
        l= [] 
        for j in range(0,len(LIST)+1):
            col = []
            for q in range(0,k+1):
                col.append(0)
            l.append(col)           # creating 2D list and filling all index with 0 elements
        for j in range(0,len(LIST)+1):
            for q in range(0,k+1):
                if(j == 0 and q!=0):
                    l[j][q] = 0       # if size of list is 0 then sum of subset will not be more than 0 so 0 refer to not possible
                elif(q == 0):
                    l[j][q] = 1       # if size of list is 0 then sum of subset is 0 is possible for {} subset (NULL subset) so 1 refer for possible
        for g in range(1,len(LIST)+1):
            for h in range(1,k+1):
                if(LIST[g-1] <= h):
                    l[g][h] = l[g-1][h-LIST[g-1]] or l[g-1][h]    # making choice over each elements of list either take it or not 
                elif(LIST[g-1] > h):
                    l[g][h] = l[g-1][h]                          # not taking elements because elements is greater than remaning k value 
        if(l[len(LIST)][k] == 1):
           return("TRUE")                                    # return TRUE if the partitioning possible (1 refer for possible)
        elif(l[len(LIST)][k] ==0):
            return("FALSE")                                     # return FALSE if partitioning not possible (0 refer for not possible)

In the above code 1 refer for POSSIBLE and 0 refer for NOT POSSIBLE.

This code is somehow related to the Knapsack Problem especially in finding the subset sum problem. So you can use that one concept also to reach till here this concept. Now I will pass LIST as an argument and show output :

li = [1,5,11,5]
li = [1,3,2,2]
print(part(li))
print(part(li))

OUTPUT:

TRUE
TRUE

I hope this article really you guys to understand this problem and try this concept and try to solve it on any coding site. It will really clear your concept more. Try t0 Dry Run this code on your own to know about what is going on behind this code. How the sub-problem is helping to get the output for the problem.

Do comment if you like this lesson and also you can give me some suggestions related to this article if required.

One response to “Equal Subset Sum Partition of Array or List in Python”

  1. Khushboo says:

    Thnk you so much your article really help me alot to understand the concept.

Leave a Reply

Your email address will not be published. Required fields are marked *