The problem and variations of the same has been frequently asked in competitions.

The goal of the program is to find equal sum subsets of a given sequence of numbers

For example :

Sequence : 3 1 3 7 5 2

Subsets : [3,1,3] [7] [5,2] with smallest possible sum of 7

If no such subset is possible the algorithm returns a subset which is the sequence itself i.e [3,1,3,7,5,2] with a sum of 21

Lets note down two important features

1. The sum has to be the **smallest**

2. The subset elements must be in **sequence**

input : 3 7 1 3 5 2 will not work as [3,1,3] is not in sequence.

**ALGORITHM**:

1. Calculate the total sum of the sequence

2. Read each element and assign it to a temporary sumA

3. check if the temporary sum is a factor of total sum

4. If it is check if remaining elements add up to be a factor

a. Do this by reading the remaining elements into another temporary sumB

if this sumB == sumA we get a subset

else the remaining set does not give factors

5. if the remaining set does not result in factor continue reading elements into sumA

6. Continue until sumB = sumA.

**TRACE**:

Let us trace inputs to clearly understand the strategy

input : 3 1 3 7 5 2

sum = 21

1. sumA = 3

2. sumA factor of 21, so check if remaining elements form subsets

3. sumB = 1

4. if ( sumB > sumA) return 0 (so that sumA can continue to take elements)

else (sumB == sumA) return 1

so , (1 > 3) returns 0

5. Now reads into sumA = 3+1 =4

6. sumA is not factor of 21 so continue reading

7. sumA = 3+1+3 = 7

8. sumA is a factor of 21, so check if remaining elements form subsets

9. sumB = 7 (remember everytime we enter to check remaining elements sumB is made 0)

10. if (sumB > sumA) sumB = 0 (this is indication that we have another subset)

11. continue with remaining sumB= 5

12. if (sumB > sumA) continue reading into sumB

13. sumB = 5+2 = 7 if (sumB == sumA) sumB=0 (indicated we have another subset)

14. if (sumB == 0) return true that we have the subset

15. Now equipped with the minimum sum value i.e sumA finding the subsets is a trivial matter. Steps 1 – 14 is only to find minsum we did not track the actual elements of the subset.

**IMPLEMENTATION** : in C

#include "stdio.h"
int data[100];
int sum = 0;
void partition(int minsum,int size);
void PrintPartition(int start,int end);
int main()
{
int i,size,minsum;
printf("Enter the number of elements\n");
scanf("%d",&size);
printf ("Enter the elements\n");
for(i=0 ;i<size ;i++)
{
scanf("%d",&data[i]);
sum+=data[i];
}
minsum = LeastPartitionSum(size);
printf("The total smallest sum of equal partition is %d\n", minsum);
printf("The partitions are : \n");
partition(minsum,size);
return 0;
}
/* Equipped with knowledge of minsum , find the exact elements */
void partition(int minsum,int size)
{
int i,sum=0,count=0,start=0;
for (i =0 ;i < size ; i++)
{
sum+=data[i];
count++;
if(sum == minsum)
{
sum = 0;
PrintPartition(start,count);
start=count;
}
}
}
/* method to print the elements in readable format */
void PrintPartition(int start,int end)
{
int i;
printf("[");
for ( i=start; i<end; i++)
{
if(i != end-1)
{
printf("%d,",data[i]);
}
else
{
printf("%d",data[i]);
}
}
printf("]\n");
}
/* method to find if remaining elements can be bunched to be factors of the total sum */
int CheckRemBunchSum(int BunchSum, int start, int size)
{
int i, RemBunchSum;
RemBunchSum = 0;
for(i = start; i < size ; i++)
{
RemBunchSum += data[i];
if(RemBunchSum > BunchSum)
{
return 0;
}
else if(RemBunchSum == BunchSum)
{
RemBunchSum = 0;
}
}
if(RemBunchSum != 0)
{
return 0;
}
return 1;
}
/* trying to find the first possible set of elements which are a factor of total sum */
int LeastPartitionSum(int size)
{
int BunchSum, i; /*bunch sums over a loop until its a factor of total sum */
for(i = 0, BunchSum = 0; (i < size) && (BunchSum <= sum/2) ; i++)
{
BunchSum += data[i];
if((sum % BunchSum) == 0)
{ /* BunchSum divides sum, so lets go ahead and check if remaining elements are factors */
if(CheckRemBunchSum(BunchSum, i+1, size))
{
return BunchSum;
}
}
}
/* if no subset is formed */
printf("There is no subset formed. We have to consider the whole array as the set\n");
return sum;
}

OUTPUT:

laptop:~/code$ ./a.out

Enter the number of elements

6

Enter the elements

3

1

3

7

5

2

The total smallest sum of equal partition is 7

The partitions are :

[3,1,3]

[7]

[5,2]

Now lets change the input to 3 1 3 6 6 2

laptop:~/code$ ./a.out

Enter the number of elements

6

Enter the elements

3

1

3

6

6

2

There is no subset formed. We have to consider the whole array as the set

The total smallest sum of equal partition is 21

The partitions are :

[3,1,3,6,6,2]

**ADDITIONAL READING**:

Related topics include NP complete problem termed Partition problem and Subset sum problem

These are problem usually solved used heuristic approach, especially for the subset sum problem that involves a greedy heuristic proposed by Kamarkar-Karp differencing algorithm

In my future posts i will post more detail of the partition and subset sum problem.

This Paper looks into various variations of the K- equal subset sum problems.

For now you might have seen how the problem statement is a heavy modification of the K- equal subset sum – NP complete problem. We made life easy by stating properties like same sequence and smallest sum with a condition that we can have the entire original sequence as a subset if we do not get any subset.

With above material,it would be interesting to brainstorm to solve the problem when there are potential correct subset with a jumbled up original sequence, [ 3 2 7 1 5 3] 😉

Thanks for reading !

### Like this:

Like Loading...

*Related*

I am doubtful for this solution in case when set is {5,5,5,2,2,2}

When I executed the code, I expected it to provide me three sets of {5,2}

Did I miss something?

The resultant set {5,2} must be in sequence. This sequence will work

laptop:~$ ./a.out

Enter the number of elements

6

Enter the elements

5

2

5

2

5

2

The total smallest sum of equal partition is 7

The partitions are :

[5,2]

[5,2]

[5,2]

I have to modify to over come this discrepancy.