The Sum of Subset problem can be give as: Suppose we are given n distinct numbers and we desire to find all combinations of these numbers whose sums are a given number ( m ).
For example, if n=4 i.e there are four numbers as: 1, 2, 3, 4, 5 and m=5 the all possible subsets are as : {1,4},{2,3},{5}
The following programs finds all subsets using backtracking:
JAVA implementation:
C Implementation:
For example, if n=4 i.e there are four numbers as: 1, 2, 3, 4, 5 and m=5 the all possible subsets are as : {1,4},{2,3},{5}
The following programs finds all subsets using backtracking:
JAVA implementation:
import java.util.Scanner; /** * * @author VIK VIKKU VIKASHVVERMA VIKASH * * @Website: http://vikash-thiswillgoaway.blogspot.com * */ public class SumOfSubsets { int[] w; int[] x; int sum; public void process() { getData(); } private void getData() { Scanner sc = new Scanner(System.in); System.out.print("Enter the number of elements:"); int n = sc.nextInt(); w = new int[n + 1]; x = new int[n + 1]; int total = 0; System.out.println("Enter " + n + " Elements :"); for (int i = 1; i < n + 1; i++) { w[i] = sc.nextInt(); total += w[i]; } System.out.println("Enter the sum to be obtained: "); sum = sc.nextInt(); if (total < sum) { System.out.println("Not possible to obtain the subset!!!"); System.exit(1); } subset(0, 1, total); } private void subset(int s, int k, int r) { int i = 0; x[k] = 1; if (s + w[k] == sum) { System.out.println(); for (i = 1; i <= k; i++) { System.out.print("\t" + x[i]); } } else if ((s + w[k] + w[k + 1]) <= sum) { subset(s + w[k], k + 1, r - w[k]); } if ((s + r - w[k]) >= sum && (s + w[k + 1]) <= sum) { x[k] = 0; subset(s, k + 1, r - w[k]); } } public static void main(String[] args) { new SumOfSubsets().process(); } }
C Implementation:
#include < stdio.h > void sumOfSub(int,int,int); static int m=0; int*w; int*x; void main() { int i=0,sum=0,n=0; printf("Enter size of array: "); scanf("%d",&n); w=(int*)malloc(sizeof(int)*n+1); x=(int*)malloc(sizeof(int)*n+1); printf("Enter %d elements: ",n); for(i=1;i < =n;i++) { scanf("%d",&w[i]); sum+=w[i]; x[i]=0; } printf("Enter the sum to be obtained: "); scanf("%d",&m); if(sum < m) { printf("Not possible to obtain any subset !!! "); exit(1); } printf("Possible Subsets are( 0 indicates exclusion and 1 indicates inclusion) : "); sumOfSub(0,1,sum); } void sumOfSub(int s,int k,int r) { int i=0; x[k]=1; if(s+w[k]==m) { printf("\n"); for(i=1;i < =k;i++) printf("\t%d",x[i]); } else if((s+w[k]+w[k+1]) < =m) { sumOfSub(s+w[k],k+1,r-w[k]); } if((s+r-w[k]) > =m && (s+w[k+1]) < =m) { x[k]=0; sumOfSub(s,k+1,r-w[k]); } }
No comments :
Post a Comment