题解 | Sum of Factorials

//因为10的阶乘就已经很大了，所以阶乘能选的数字很少
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
//还有个0的阶乘别忘了所以有两个1可以用
int a[] = {1,1, 2, 6,42,1806,3263442};//存下所有阶乘之后开始暴搜
bool visit[8];
bool dfs(int sum, int aim) {
    if (sum > aim)return false;
    if (sum == aim)return true;
    bool isfind = false;//代表当层是否有答案
    for (int i = 0; i < 6; i++) {
        if (!visit[i]) {
            //该阶乘没有被选过
            visit[i] = true;
            if (dfs(sum + a[i], aim)) {
                //找到结果
                isfind = true;
            }
            visit[i] = false;

        }
    }
    return isfind;
}
int main()
{
    // long long n=1;
    // while(n<1e9){
    //     cout<<n<<',';
    //     n*=(n+1);
    // }
    int n;
    while (cin >> n) {
        if (n < 0)break;
        if (dfs(0, n))puts("YES");
        else puts("NO");
    }
}