Saturday, May 12, 2012

Sum of Subsets (find all sums for given Number set)



Sample Output is shown above. This program will run in windows only. For Linux you must write your own gotoxy function.

#include<stdio.h>
#include<stdlib.h>

#define MAX_PRINT_LEVEL 5

#include <windows.h>

void gotoxy(int col, int row)     //starting from 0
{
    COORD coord;
    coord.X = col;
    coord.Y = row;

    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}

struct tree_node
{
       struct tree_node *left,*right;
       int data;
};

typedef struct tree_node TNODE;

TNODE* create_tree(int *input,int num);
void add_num(TNODE *node,int *input,int num);
void print_tree(TNODE *root,int num,int col,int row);
int print_subsets(TNODE *root,int sum,int *input,int *subsets,int index,int num);
int pow(int a, int b);

//array to store all possible sums, remove if not neeeded
/*int *sums,sum_count=0;*/

int main()
{
       int sum;

       int *input,num;
       int *subsets;
       TNODE *root=NULL;



       int i;

       printf("\nHOW MANY NUMBERS: ");
       scanf("%d",&num);
       if(num<0)
       {
              printf("\nERROR: Invalid num value...\n\n");
              exit(1);
       }
       if( (input = (int*)malloc(num*sizeof(int))) == NULL)
       {
              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");
              exit(1);
       }
       if( (subsets = (int*)malloc(num*sizeof(int))) == NULL)
       {
              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");
              exit(1);
       }
       printf("\nEnter numbers: \n");
       for(i=0;i<num;i++)
       {
              printf("NUM[%d] : ",i);
              scanf("%d",&input[i]);
       }

       //array to store all possible sums, remove if not neeeded
       /*if( (sums = (int*)malloc(pow(2,num)*sizeof(int))) == NULL)
       {
              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");
              exit(1);
       }*/

       root = create_tree(input,num);

       system("cls");
       print_tree(root,num,0,0);
       printf("\n\nINPUT ARRAY :");
       for(i=num-1;i>=0;i--)
              printf(" %d",input[i]);
      
       printf("\n\n");

       //print all sums possible
       /*for(i=sum_count-1;i>=0;i--)
       {
              if(print_subsets(root,sums[i],input,subsets,num,num))
                     printf("\n********** SUBSETS WITH SUM = %d **********",sums[i]);
       }*/


       //print  a particular sum
       printf("\n\nENTER SUM: ");
       scanf("%d",&sum);
       printf("\n********** SUBSETS WITH SUM = %d **********",sum);
       if(!print_subsets(root,sum,input,subsets,num,num))
              printf("\n\nOOPS : NO SUBSET CAN BE FOUND");

       printf("\n\n\n");
       return 0;
}

int print_subsets(TNODE *node,int sum,int *input,int *subsets,int index,int num)
{
       int i,found=0,a,b;

       if(node->left==NULL && node->right == NULL)
       {
              if(node->data == sum)
              {
                     printf("\n{ ");
                     for(i=0;i<num;i++)
                           if(subsets[i] == 1)
                           {
                                  found = 1;
                                  printf("%d,",input[i]);
                           }

                     if(found)
                           printf("\b } ");
                     else
                           printf("NULL SET }");

                     return 1;
              }
              else
                     return 0;
       }
       if(node->left)
       {
              subsets[index-1] = 1;
              a=print_subsets(node->left,sum,input,subsets,index-1,num);
       }
       if(node->right)
       {
              subsets[index-1] = 0;
              b=print_subsets(node->right,sum,input,subsets,index-1,num);
       }

       return (a||b);
}

void print_tree(TNODE *root,int level,int col,int row)
{
       int gap,pos,slash;
       int i;
       int bcol,brow;

       if(level>MAX_PRINT_LEVEL)
       {
              printf("\nTree cant be displayed for level > %d...",MAX_PRINT_LEVEL);
              return;
       }
       gap = pow(2,level) - 1;
       bcol = col;
       brow = row;

       col=col+gap;
       gotoxy(col,row);

       printf("%d",root->data);
       if(root->left)
       {
              slash = pow(2,level-1);
              for(i=0;i<slash;i++)
              {
                     gotoxy(--col,++row);
                     printf("/");
              }
              print_tree(root->left,level-1,bcol,row+1);
       }
       if(root->right)
       {
              col = bcol+gap;
              row = brow;
              slash = pow(2,level-1);
              for(i=0;i<slash;i++)
              {
                     gotoxy(++col,++row);
                     printf("\\");
              }
              if(level>1)
                     print_tree(root->right,level-1,bcol+gap+1,row+1);
              else
                     print_tree(root->right,level-1,bcol+gap+1,row+2);
       }
}

int pow(int a, int b)
{
       int ans=1;

       if(b==0)
              return 1;

       while(b>0)
       {
              ans = ans * a;
              b--;
       }

       return ans;
}

TNODE* create_tree(int *input,int num)
{
       TNODE *temp;
       int i;

       temp = (TNODE*)malloc(1*sizeof(TNODE));
       temp->data=0;
       temp->left=NULL;
       temp->right=NULL;

       add_num(temp,input,num);

       return temp;
}

void add_num(TNODE *node,int *input,int num)
{
       if(num == 0)
       {
              //array to store all possible sums, remove if not neeeded
              /*sums[sum_count++] = node->data;*/

              return;
       }

       node->left=(TNODE*)malloc(1*sizeof(TNODE));
       node->right=(TNODE*)malloc(1*sizeof(TNODE));

       node->left->data = node->data + input[num-1];
       node->left->left = NULL;
       node->left->right = NULL;

       node->right->data = node->data + 0;
       node->right->left = NULL;
       node->right->right = NULL;

       add_num(node->left,input,num-1);
       add_num(node->right,input,num-1);
}

Posted by at
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)