算法DFS

有一个问题一直不知道就是当数组小于16的时候答案挖掉，

但是如果在check里面加上if(b < 0)return false;答案正确
我想可能是负数的原因，不知道哪位大佬 可以帮我解答一下~~

blablabla

时间复杂度

参考文献

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
bool st[N], g[N];
int ans;

bool check(int a, int c)
{
    int b = n * c - a * c;

    if (!a || !b || !c) return false;

    memcpy(g, st, sizeof st);
    while (b)
    {
        int x = b % 10;     // 取个位
        b /= 10;    // 个位删掉
        if (!x || g[x]) return false;
        g[x] = true;
    }

    for (int i = 1; i <= 9; i ++ )
        if (!g[i])
            return false;

    return true;
}

void dfs_c(int u, int a, int c)
{
    if (u == 9) return;

    if (check(a, c)) ans ++ ;

    for (int i = 1; i <= 9; i ++ )
        if (!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
}

void dfs_a(int u, int a)
{
    if (a >= n) return;
    if (a) dfs_c(u, a, 0);

    for (int i = 1; i <= 9; i ++ )
        if (!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
}


int main()
{
    cin >> n;

    dfs_a(0, 0);

    cout << ans << endl;

    return 0;
}