c++ - 使用加法、减法和连接将数字组合成给定数字的方法

Question

我已经通过暴力检查所有组合以我自己的方式解决了这个 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;
}

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

Answer 1

应对所有此类挑战的诀窍是不要将相同的工作做两次。也就是说，12345678-9、12345678+9和12345678 * 10 + 9都共享相同的逻辑来计算12345678 。

有很多方法可以实现这一点，但递归解决方案就足够合理了。