1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139


#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;
}
View Program Text


Test Status