c++ - 使用加，减和级联将数字组合成给定数字的方法

我已经通过蛮力检查所有组合来解决了c++练习。我想知道是否有更好，更优雅和/或更短/更快的解决方案？

这是翻译后的问题:(“无”指的是串联)

/*

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

*/

这是我的解决方案:

#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;
}

我听说可能有一个简短的递归解决方案，我想知道您将如何解决这种问题，和/或是否有一个甚至更好的解决方案，又如何“看到”呢？

最佳答案

解决所有这些挑战的诀窍是不要做两次相同的工作。也就是说，12345678-9，12345678+9和12345678 * 10 + 9都具有相同的逻辑来评估12345678。

有许多方法可以实现这一点，但是递归解决方案是足够合理的。