subsetsum.c

/*This code print all the subset of a given set whose sum of element = k*/
/*'k' is provided by user*/
/* first line of input is n integers which are elements of set
    secone line is sum
Input
    1,2,3,4
    5
Output
    (1,4),(2,3)
    */


#include<stdio.h>
#include<math.h>
#include<malloc.h>
//#define ARRAYSIZE(x) sizeof(x)/sizeof(x[0])

int * subsetsum(int * , int);
void subset(int* set, int arraysize, int n);

int main()
{
    int *set,*set1,*set2,*sum1,*sum2;
    int arraysize,i,j,k,m=0,found=0;
    int set1size,set2size;
    printf("Enter number of elements in array: ");
    scanf("%d",&arraysize);
    /*Bifurcatiing array */
    set1size = arraysize/2;
    set2size = arraysize - arraysize/2;
    /*dynamically allocating memories*/
    set = calloc(arraysize, sizeof(int));
    set1 = calloc(set1size, sizeof(int));
    set2 = calloc(set2size, sizeof(int));

    /*filling the array elements by users*/
    printf("\nNow enter all the elements which must be unique: \n");
    for(i=0;i<arraysize;i++)
        {
            printf("Enter element %d: ",i+1);
            scanf("%d",&set[i]);
            if(i<arraysize/2)
            /*Bifuracating the set into two parts almost equal length*/
                set1[i] = set[i];
            else
            /*since m=0 hence set2 start filling from oth element*/
                set2[m++] = set[i];
        }
    printf("\n\nEnter the sum: ");
    scanf("%d",&k);
    /*Subsetsum is a fun which return an array which contain sum of all the subset elements*/
         sum1 = subsetsum(set1, set1size);
         sum2 = subsetsum(set2, set2size);
         printf("\nThe set is following: \n");
         printf(" (");
         for(i=0;i<arraysize;i++)
            printf("%d,",set[i]);
            printf("\b ");
            printf(")");

        printf("\n\n\nAll the subsets whose sum = %d is following: \n\n",k);
        for(i=0;i<pow(2,set1size);i++)//traversing in set1 subset
            for(j=0;j<pow(2,set2size);j++)//traversing in set2 subset
               if(sum1[i] + sum2[j] == k)
    /*now we know that ith subset of set1 & jth subset of set2 makes the sum*/
    /*Now we will find the ith & jth subset and will print it*/
                    {   found++;//indicate that the sum has been found
                        printf(" ( ");
                        /*subset is a fun which print the ith subset of a given array*/
                        subset(set1,set1size,i);
                        printf(",");
                        subset(set2,set2size,j);
                        printf(" ),");
                     }
                     printf("\b ");
        if(found)
            printf("\nThe required subset printed above: ");
        else
            printf("\nNo such subset found: ");

free(sum1);
free(sum2);
free(set);
free(set1);
free(set2);
return 0;
}//main

int * subsetsum(int * set, int arraysize)
    {
        int i,j,sum;
        int *ptr;
        ptr = calloc(pow(2,arraysize), sizeof(int));
        for(i=0;i<pow(2,arraysize);i++)
        {   sum=0;

            for(j=0;j<arraysize;j++)
    /*if array has 'n' elements then check all 'n' bits of i (from 0 to n-1) either it is set or not*/
    /*if jth bit of i is set then array[j] will be printed as subset*/
                if((1<<j) & i)
                    {
                       sum = sum + set[j];
                    }
                ptr[i] = sum;


        }
        return ptr;
    }//end of subsetsum

/*The following function print the nth subset of a given set*/

void subset(int* set, int arraysize, int n)
    {
        int j,count=0;
        for(j=0;j<arraysize;j++)
            if((1<<j) & n )
                {
                    if(count>0)
    /*if this 'j' loop run more than 1 time it will put ',' between two value printed*/
                        printf(",");
                    count++;
                    printf("%d",set[j]);
                }

    }//end of subset