Ways of combining digits to a given number using addition, subtraction and concatenation

user_5821790 0
Viewed 131

I've solved this c++ exercise by brute force checking all combinations in my own way.
I'm wondering if there's a better, more elegant, and/or shorter/faster solution?

Here's the translated problem: ("nothing" refers to concatenation)

/*

Write a program that outputs the number of possible ways to:
Combine ascending digits 1...9 using +, -, and "nothing" to get the result of input x.

Example:
Input: 100
Output: 11

(That's because we have 11 ways to get 100:)
123 - 45 - 67 + 89 = 100 
123 + 4 - 5 + 67 - 89 = 100 
123 + 45 - 67 + 8 - 9 = 100 
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 

*/

Here's my solution:

#include<iostream>
using namespace std;


int power(int a, int n) {
    int rez = 1;
    for (int i = 0; i<n; i++) {
        rez *= a;
    }
    return rez;
}

void makeCombo(int c, int C[]) {
    int digit = 0;
    while (c != 0) {
        C[digit] = c % 3;
        c /= 3;
        digit++;
    }
}

bool testCombo(int C[], int x) {
    int a = 9;
    int sum = 0; 
    int concatenator = 0;
    int concatenation = 0;

    for (int i = 0; i < 8; i++) {
        if (C[7-i] == 0) {
            concatenator += a*power(10,concatenation);
            concatenation++;
        } else if (C[7-i] == 1) {
            sum += a*power(10,concatenation);
            sum += concatenator;
            concatenator = 0;
            concatenation = 0;
        } else if (C[7-i] == 2) {
            sum -= a*power(10,concatenation); 
            sum -= concatenator; 
            concatenator = 0;
            concatenation = 0;
        }
        a--;
    }
    sum += a*power(10,concatenation);
    sum += concatenator;

    return (sum == x);
}

int main() {
    int x, count = 0;
    cin >> x;

    int combo = 0;
    int C[8] = {0,0,0,0,0,0,0,0}; 
    while (combo < power(3,8)) {
        makeCombo(combo, C);
        if (testCombo(C, x)) { count++; }
        combo++;
    }

    cout << count << endl;
    return 0;
}


I've heard that there's a short recursive solution possible and I'm wondering how you would solve this like that, and/or is there an even "better" solution, and how can you "see it"?

algorithm c++
3 Answers

The trick to all such challenges is not to do the same work twice. That is to say, 12345678-9, 12345678+9 and 12345678 * 10 + 9 all share the same logic to evaluate 12345678.

There are many ways in which this can be achieved, but a recursive solution is reasonable enough.

MSalters_154160

Update: This is not my solution but is the recursive one I've heard about. Way faster than my initial solution, and very elegant.

#include <iostream>
using namespace std;

int x;

int count(int n, int num, int sum) {

    if (n == 9) { return sum + num == x; }

    int next = n + 1;
    int counter = 0;

    counter += count(next, next, sum + num);
    counter += count(next, -next, sum + num);

    num *= 10;
    if (num < 0)
        num -= next;
    else
        num += next;

    counter += count(next, num, sum);
    return counter;
}

int main(int x) {
    cin >> x;
    cout << count(1, 1, 0) << endl;
    return 0;
}
user_58217900

Here you can find a full working recursive sample:

I wrote two recursive methods,

test_combo - to evaluate the combo

make_combo - to generate the combo 

#include<iostream>
using namespace std;
//recursivly evaluate the combo.
int test_combo( const std::string& s, int sign)
{ 
    size_t next_pos = s.find_first_of("+-");
    int sum = sign * strtol(s.substr(0,next_pos).c_str(),0,0);;
    if(next_pos == string::npos)
    {
        return sum;
    }
    else
    {   
        char op = s[next_pos];
        switch(op)
        {
           case '+':
              sum+=test_combo(s.substr(next_pos+1),1);
              return sum;
           case '-':
              sum+=test_combo(s.substr(next_pos+1),-1);
              return sum;
        }
    }
}
//recursivly build the combo.
void make_combo(int n, const std::string& s )
{
    if(n==10)
    {
        int sum=test_combo(s,1);
        if(sum==100)
            cout<<s<<"="<<sum<<endl;
    }
    else
    {
        char next_digit = '0'+n;          //we have 3 options:
        make_combo(n+1,s+next_digit);     //append next digit with no op
        make_combo(n+1,s+'+'+next_digit); //append next digit with + op
        make_combo(n+1,s+'-'+next_digit); //append next digit with - op
    }
}

int main()
{
    make_combo(2,"1");//string always start with a '1'
    return  0;
}
user_28521650
Related