Problem:
In a given array a = {1, 7, 3, 4, 5, 6, 2} Print the indices of all the combinations which lead to a given sum called target. For e.g. if the method is
Void PrintAllSumCombos(int[] arr, int target) - and the array shown above is passed with sum target = 7, then the output should be:
0, 3, 6
0, 5
1
2, 3
4, 6
Note: For simplicity, You may assume the array does not contain any negative numbers and also consider same set of indices with a different order as identical - for e.g. if 2, 3 is already printed, ignore 3, 2 as they are one and the same.
Solution:
A simple and straightforward solution is to examine all possible combinations recursively, and print those that sum up to the target:
void PrintAllSumCombos(int arr[], int target,int start,int taken[],int count) {
if (target==0) {
for (int i =0;i<count;i++) {
cout << taken[i] << " ";
}
cout << "\n";
return ;
}
if (target ==-1 || start > 7) {
return ;
}
for(int i=start; i < 7 ;i++) {
taken[count]=i;
}
}
int main() {
int a[7]={1, 7, 3, 4, 5, 6, 2};
int b[7];
PrintAllSumCombos(a, 7,0,b,0) ;
return 0;
}
However, there must exist a more efficient dynamic programming solution. Basic idea: examine each element of the array. Drop those that are greater than the target (because all the elements are non-negative). Also drop all elements equal to the target and print their indexes (tricky part if we should account for zeroes, but this is doable - just don't drop the elements that are equal to the target then). Now we're left with items that are less than the target. We must now produce all possible pairs, remembering the indexes of the pair elements, calculate their sum and perform the same procedure as for single elements (dropping/printing the pairs as necessary). So we end up with a list of pairs with sums less than the target. Continue this until the list is empty. The worst case time complexity of this algorithm is still O(n ^ 2), however, in average case it must be more efficient because we examine less and less elements on each step due to dropping those that are too large.
Complexity:
time - O(n ^ 2)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=21383667
