考研机试 阶乘的和
给定一个非负整数 n，请你判断是否存在一些整数 xi，能够使得 n=∑1≤i≤txi!，其中 t≥1,xi≥0,xi=xj iff i=j。iff表示当且仅当。
输入格式
输入包含多组测试数据。
每组数据占一行，包含一个非负整数 n。
最后一行是一个负数，表示输入结束，无需处理。
输出格式
每组数据输出一行结果，如果 n
能表示为若干数的阶乘之和，则输出 YES，否则输出 NO。
数据范围
0≤n≤106,
每组输入最多包含 100组数据。
输入样例：
9
-1
用set空间换时间 把所有可能性都生成好
#include <stdio.h>
#include <set>
#include <vector>
using namespace std;
int main(){
vector<int> fA;
fA.push_back(1);
int curfA=1;
for(int i=1;i<=9;++i){
curfA=curfA*i;
fA.push_back(curfA);
}
set<int> allpossible;
allpossible.insert(0);
for(int i=0;i<=9;++i){
set<int> tempSet;
set<int>::iterator it;
for(it=allpossible.begin();it!=allpossible.end();++it){
tempSet.insert(*it+fA[i]);
}
for(it=tempSet.begin();it!=tempSet.end();++it){
allpossible.insert(*it);
}
}allpossible.erase(0);
int n;
while(scanf("%d",&n)!=EOF){
if(n<0){
break;
}
//需要计算从0！开始计算阶乘 和至少有一项
//xi=xj,i=j 阶乘不能重复 阶乘范围小于100万 阶乘的范围是0到9的阶乘
if(0==allpossible.count(n)){
printf("NO\n");
}else if(1==allpossible.count(n)){
printf("Yes\n");
}
}
}
思路 利用set将所有的情况都提前存储 根据每个输入的数据在set中查找
