/* * Array a[] = Array to hold elements in set. * howManyNoInSet = Size of set (k). * size = Elements in input array. * sum = Total sum of elements included in resulting set. * spaceLeft = Number of elements included in set currently. * pos = Index in input array. * Total = given number S. * * Eg. Input : arr[] ={1,0,-1,2,-2,3} * k = 3 * S = 0 * Sets : * (1,0,-1) * (0,2,-2) * (-1,-2,3) */ /* * RECURSIVE ALGORITHM * 1. if pos (current index of input array) is greater than equal to size of array * then return as it is not a valid element of input array. * 2. if set contains k(howManyNoInSet) elements and sum of these k elements = given Number S. * i.e. if ( spaceLeft == 0 && sum == 0) then * we have found a solution. * 3. Else the solution doesn't matches our criteria and is discarded. * 4. Now, make 2 recursive calls: * a. Not Including the current element in set. * RecurssiveSumCheck(pos+1, spaceLeft, sum) * b. Including the current element in set. * Since current element is included in set spaceLeft dicreases by 1 and sum also dicreases by value of current element. * RecurssiveSumCheck(pos+1, spaceLeft-1, sum-arr[pos+1]); */ #include<iostream> using namespace std; int arr[]={-1,0,1,2,-2,4,-4,5,-5}; int size = sizeof(arr)/sizeof(arr[0]); int *a; int startIndex = -1, howManyNoInSet =3, Total = 0; void RecurssiveSumCheck(int pos, int spaceLeft , int sum) { if(pos >= size) return ; if(spaceLeft == 0 && sum == 0) { cout<<endl; for(int i =0;i<howManyNoInSet ; i++) cout<<" "<<a[i]; return ; } if(spaceLeft == 0 && sum !=0 ) return; RecurssiveSumCheck(pos+1, spaceLeft, sum); a[howManyNoInSet-spaceLeft]=arr[pos+1]; RecurssiveSumCheck(pos+1, spaceLeft-1, sum+arr[pos+1]); } int main() { a = new int[howManyNoInSet]; RecurssiveSumCheck(startIndex,howManyNoInSet,Total); }
Sunday, 13 January 2013
Find all the sets of length k in an array such that the sum of all the elements of set is equal to a given number S.
Subscribe to:
Post Comments (Atom)
The problem is NP-hard...
ReplyDeleteWorst case exponential... but we can also intelligentlly prune out the search space using intelligent ways
Please do mention the algorithm also before writing the code
I have now included the explanation.
ReplyDeleteHope it helps.