题目链接

Backward Digit Sums POJ - 3187

思路

全排列然后用杨辉三角判定。

时间复杂度

$$ O(N*(N!)) $$

代码1 dfs

#include <cstdio>

using namespace std;

const int MAXN = 15;

int yang[MAXN][MAXN];
bool f = false;
int n, sum;
int vis[MAXN], a[MAXN];

void dfs(int x) {
    if (f) {
        return;
    }
    if (x > n) {
        int cur = 0;
        for (int i = 1; i <= n; i++) {
            cur += yang[n][i] * a[i];
        }
        if (cur == sum) {
            f = true;
            for (int i = 1; i <= n; i++) {
                if (i == 1) {
                    printf("%d", a[i]);
                } else {
                    printf(" %d", a[i]);
                }
            }
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = 1;
            a[x] = i;
            dfs(x + 1);
            vis[i] = 0;
        }
    }
}
int main() {
    yang[1][1] = 1;
    for (int i = 2; i <= 10; i++) {
        for (int j = 1; j <= i; j++) {
            yang[i][j] = yang[i - 1][j - 1] + yang[i - 1][j];
        }
    }
    scanf("%d%d", &n, &sum);// don't forget &
    dfs(1);
    return 0;
}

代码2 next_permutation版

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 15;

int yang[MAXN][MAXN];
bool f = false;
int n, sum;
int a[MAXN];

int main() {
    yang[1][1] = 1;
    for (int i = 2; i <= 10; i++) {
        for (int j = 1; j <= i; j++) {
            yang[i][j] = yang[i - 1][j - 1] + yang[i - 1][j];
        }
    }
    scanf("%d%d", &n, &sum);// don't forget &
    for (int i = 1; i <= n; i++) {
        a[i] = i;
    }
    do {
        int cur = 0;
        for (int i = 1; i <= n; i++) {
            cur += yang[n][i] * a[i];
        }
        if (cur == sum) {
            f = true;
            for (int i = 1; i <= n; i++) {
                if (i == 1) {
                    printf("%d", a[i]);
                } else {
                    printf(" %d", a[i]);
                }
            }
            break;
        }
    } while(next_permutation(a + 1, a + 1 + n));

    return 0;
}