题目描述(上交考研机试题)

给定一个非负整数 n，请你判断是否存在一些整数 xi，能够使得 n 为这些数的阶乘之和，其中 xi≥0,xi=xj iff i=j。

iff 表示当且仅当。

样例

输入样例
最后一行是一个负数,表示输入结束;

9
-1

输出样例

YES

数据范围
0≤n≤10^6,
每组输入最多包含 100 组数据。

解题思路

• 因为10的阶乘已经大于10^6,故取值范围只有1到9的阶乘;
• 对此题,可以将所有可能的结果均列出来组成一个集合,最后仅需要查询输入的数是否在集合中即可;
• 使用dfs构建阶乘的集合;

#include<iostream>
#include<unordered_set>
using namespace std;

int a[10];
unordered_set<int> hs;

void dfs(int i, int u){
    if(i == 10){
        if(u != 0)
            hs.insert(u);
        return;
    }
    dfs(i + 1, u + a[i]);
    dfs(i + 1, u);
}

int main()
{
    a[0] = 1;
    for(int i = 1; i < 10; ++i) a[i] = i * a[i-1];
    dfs(0, 0);
    int n;
    while(cin>>n){
        if(n >= 0){
            if(hs.count(n))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}