题解 | #Sum of Factorials#

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> num;
map<int, bool> m; //存储0!~9!能够组合出来哪些正整数n

void init() {
    num.push_back(1);//0!=1
    int k = 1;
    for (int i = 1; k <= 1e6; i++) {
        k *= i;
        num.push_back(k);
    }
}

void dfs(int u, int sum) {
    if (u == num.size()) {
        m[sum] = true;
        return ;
    }
    dfs(u + 1, sum); //不选当前数
    dfs(u + 1, sum + num[u]); //选当前数
}
int main() {
    int n;
    init();
    dfs(0, 0);
    while (cin >> n && n >= 0) {
        if (n && m[n]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}