#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int totalCalls;

vector<vector<int> > results;

void CombinationSum(vector<int> &num, int index, int target, vector<int>& result)
{
	totalCalls++;
	if (target == 0)
	{
		results.push_back(result);
		return;
	}
	
	if (num.size() == index) return;
	
	CombinationSum(num, index+1, target, result);

	int n = num[index];
	int canUse = target / n;
	for (int i = 1; i <= canUse; ++i)
	{
		result.push_back(n);
		CombinationSum(num, index+1, target-i*n, result);
	}

	result.erase(result.end()-canUse, result.end());
}

vector<vector<int> > CombinationSum(vector<int> &num, int target) 
{
	totalCalls = 0;
	results.clear();
	vector<int> result;
	CombinationSum(num, 0, target, result);
	return results;
}

/********************* Combination Count *********************/

vector<vector<int> > cache;
int CombinationCount(vector<int> &num, int index, int target)
{
	totalCalls++;
	
	//for the last number, the count is just depened on whether
	//the target can be divived by it
	if (index == num.size()-1)
		return  target % num[index] == 0? 1 : 0;
	
	if (cache[index][target] < 0)
	{
		int count = 0;
		int n = num[index];
		int canUse = target / n;
		for (int i = 0; i <= canUse; ++i)
			count += CombinationCount(num, index+1, target-n*i);
		
		cache[index][target] = count;
	}
	
	return cache[index][target];
}

int CombinationCount(vector<int> &num, int target) 
{
	totalCalls = 0;
	cache = vector<vector<int> >(num.size(), vector<int>(target+1, -1));
	return CombinationCount(num, 0, target);
}

void PrintVV(vector<vector<int> > & v)
{
	for (int i = 0; i < v.size(); ++i)
	{
		cout << i+1 << ":\t";
		for (int j = 0; j < v[i].size(); ++j)
			cout << v[i][j] << ',';
		cout << endl;
	}

	cout << endl;
}

int main(int argc, char** argv)
{
	int A[] = {1,2,5,10};
	int aTarget = 17;
	vector<int> Av;
	for (int i = 0; i< sizeof(A)/sizeof(int); ++i)
		Av.push_back(A[i]);
	
	CombinationSum(Av, aTarget);
	PrintVV(results);
	cout << "Total Calls:" << totalCalls << endl << endl;
	
	cout << CombinationCount(Av,aTarget) << endl;
	cout << "Total Calls:" << totalCalls << endl << endl;

	//Second test stub
	int B[] = {
		28,22,43,41,21,29,27,38,47,23,20,49,24,31,37,26,32,36,25,33,40,46,30,44,35
	};
	int bTarget = 74;
	vector<int> Bv;
	for (int i = 0; i< sizeof(B)/sizeof(int); ++i)
		Bv.push_back(B[i]);
	//sort(Bv.begin(), Bv.end());
	
	CombinationSum(Bv, bTarget);	
	PrintVV(results);
	cout << "Total Calls:" << totalCalls << endl << endl;

	
	cout << CombinationCount(Bv,bTarget) << endl;
	cout << "Total Calls:" << totalCalls << endl << endl;

	int C[] = {71,79,97,107,81,87,70,102,92,95,80,83,84,91,119,111,89,86,108,98,104,88,82,116,73,74,90,117,85,75,93,99,100,112,78,72,114,96};
	int cTarget = 362;
	vector<int> Cv;
	
	for (int i = 0; i< sizeof(C)/sizeof(int); ++i)
		Cv.push_back(C[i]);
	
	CombinationSum(Cv, cTarget);	
	PrintVV(results);
	cout << "Total Calls:" << totalCalls << endl << endl;
	
	
	cout << CombinationCount(Cv,cTarget) << endl;
	cout << "Total Calls:" << totalCalls << endl << endl;
	
	return 0;
}