## Thursday, May 6, 2010

### C++ exercise: Recursion example -- sum up numbers

Q: Given a Sum and a string of numbers, add minimum operator "+" to make the sum of numbers equal to Sum. e.g. Sum=9, numbers: 101124, we get 9=1+01+1+1+2+4; Sum=88, numbers: 2112331453, we get 88=21+12+33+14+5+3.

```#include <string>
#include <stack>
#include <iostream>

using namespace std;

// Returns: 0 -- Got a solution.
//         -1 -- No solution.
int Calculate(int sum, string numbers,
int& best_op_count, string& best_solution)
{
//cout << " Enter: " << sum << " " << numbers <<  endl;;

bool gotone = false;
int pow10 = 1;
stack<char> tail_nums;

// Pop maximum digits from tail of "numbers".
// All the digits form a "num".
int last_num;
int num = 0;
while (num < sum && numbers.size() > 0)
{
char last_ch = *(numbers.rbegin());
last_num = last_ch - '0';
if (num + last_num * pow10 > sum)
break;

tail_nums.push(last_ch);
numbers.erase(numbers.size() - 1);
num += last_num * pow10;
pow10 *= 10;
}

if (numbers.size() == 0 && num == sum)
{
// Got one solution done.
best_op_count = 0;
best_solution = "";
while (tail_nums.size() > 0)
{
best_solution += tail_nums.top();
tail_nums.pop();
}
return 0;
}

// loop_1:
int op_count;
int temp_best_op_count = -1;
string solution;
string temp_best_solution = "";
while ( pow10 > 0 && num > 0 && tail_nums.size() > 0)
{
//cout << " ... " << sum << "(=)" << numbers << "(+)" << num << endl;

// Calculate result from the rest heading numbers as "subres".
int subres = Calculate((sum - num), numbers, op_count, solution);

// If "subres" == 0, we have a solution.
if ( ! subres )
{
gotone = true;

op_count++;  // one more op for "num" + Calculate(subsum);

//cout << "Got one solution: " << sum << "=" << solution << "+" << num
//     << " <=============================" << op_count << "(+)s" << endl;

// If it is a better solution, save it.
if (op_count < temp_best_op_count || temp_best_op_count < 0)
{
temp_best_op_count = op_count;
temp_best_solution = solution + "+";
stack<char> temp_tail_nums = tail_nums;
while (temp_tail_nums.size() > 0)
{
temp_best_solution += temp_tail_nums.top();
temp_tail_nums.pop();
}
}
}

// Remove the most significant digit from "num" back to "numbers".
if (tail_nums.size() > 0)
{
char most_sig_char = tail_nums.top();
tail_nums.pop();
numbers += most_sig_char;

pow10 /= 10;
num -= (most_sig_char - '0') * pow10;
}

// Go to loop_1.
}

best_solution = temp_best_solution;
best_op_count = temp_best_op_count;

//cout << " Exit: " << sum << " " << numbers << " gotone?" << gotone
//     << "(" << best_solution << ")" << " count(" << best_op_count << ")" << endl;;

if (gotone)
return 0;
else
return -1;
}

int main()
{
int mysum;
string mystr;
int op_cnt;
string solution;

while (cin)
{
cout << "Input sum: ";
cin >> mysum;
cout << endl;

cout << "Input string: ";
cin >> mystr;
cout << endl;

int res = Calculate(mysum, mystr, op_cnt, solution);
if (res)
cout << "No solution." << endl;
else
cout << "Solution: " << solution << endl;

cout << endl;
}

return 0;
}
```