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
numbers between 1 and n
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
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Print the indices of all the combination
Created Date : 10-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
void PrintIndice(int* arr, int len, int target, int index, vector<int>& indices)
{
if(target == 0)
{
for(int i = 0; i < indices.size(); ++i){
cout << setw(4) << indices[i];
}
cout << endl;
return;
}
for(int i = index; i < len; ++i){
if(target >= arr[i]){
indices.push_back(i);
PrintIndice(arr, len, target - arr[i], i + 1, indices);
indices.pop_back();
}
}
}
void FindIndicesCombination(int* arr, int len, int target)
{
if(target < 1 || target > len * (len + 1) / 2){
cout << "Nothing is found" << endl;
}
for(int i = 0; i < len; ++i){
vector<int> indices;
indices.push_back(i);
PrintIndice(arr, len, target - arr[i], i + 1, indices);
indices.pop_back();
}
}
void DoTest(int* arr, int len, int target)
{
if(arr == NULL){
cout << "The array is null " << endl;
cout << "------------------------------" << endl;
return;
}
if(len < 1){
cout <<"The array is empty " << endl;
cout << "------------------------------" << endl;
return;
}
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
cout << "The target sum is " << target << endl;
FindIndicesCombination(arr, len, target);
cout << "------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1, 7, 3, 4, 5, 6, 2};
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 7);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 0);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 1);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 28);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 29);
DoTest(arr, -1, 7);
DoTest(arr, 0, 7);
int* arr1 = NULL;
DoTest(arr1, 0, 7);
return 0;
}
Output
The array is
1 7 3 4 5 6 2
The target sum is 7
0 3 6
0 5
1
2 3
4 6
------------------------------
The array is
1 7 3 4 5 6 2
The target sum is 0
Nothing is found
------------------------------
The array is
1 7 3 4 5 6 2
The target sum is 1
0
------------------------------
The array is
1 7 3 4 5 6 2
The target sum is 28
0 1 2 3 4 5 6
------------------------------
The array is
1 7 3 4 5 6 2
The target sum is 29
Nothing is found
------------------------------
The array is empty
------------------------------
The array is empty
------------------------------
The array is null
------------------------------
Press any key to continue . . .