We use the backtracking method to solve this problem. Backtracking is the refinement method of Brute-Force method. Backtrack method means it finds the number of sub solutions and each may have number of sub divisions, and solution chosen for exactly one.
Backtracking method is a recursive method.
C Program
#include<stdio.h> #include<conio.h> #define TRUE 1 #define FALSE 0 int inc[50],w[50],sum,n; int promising(int i,int wt,int total) { return(((wt+total)>=sum)&&((wt==sum)||(wt+w[i+1]<=sum))); } /* * You can find this program on GitHub * https://github.com/snadahalli/cprograms/blob/master/subsets.c */ void main() { int i,j,n,temp,total=0; clrscr(); printf("\n Enter how many numbers:\n"); scanf("%d",&n); printf("\n Enter %d numbers to th set:\n",n); for (i=0;i<n;i++) { scanf("%d",&w[i]); total+=w[i]; } printf("\n Input the sum value to create sub set:\n"); scanf("%d",&sum); for (i=0;i<=n;i++) for (j=0;j<n-1;j++) if(w[j]>w[j+1]) { temp=w[j]; w[j]=w[j+1]; w[j+1]=temp; } printf("\n The given %d numbers in ascending order:\n",n); for (i=0;i<n;i++) printf("%d \t",w[i]); if((total<sum)) printf("\n Subset construction is not possible"); else { for (i=0;i<n;i++) inc[i]=0; printf("\n The solution using backtracking is:\n"); sumset(-1,0,total); } getch(); } void sumset(int i,int wt,int total) { int j; if(promising(i,wt,total)) { if(wt==sum) { printf("\n{\t"); for (j=0;j<=i;j++) if(inc[j]) printf("%d\t",w[j]); printf("}\n"); } else { inc[i+1]=TRUE; sumset(i+1,wt+w[i+1],total-w[i+1]); inc[i+1]=FALSE; sumset(i+1,wt,total-w[i+1]); } } }