阶数的和（AcWing3481）

原文链接：https://www.acwing.com/problem/content/3484/

//阶乘的和
//思路：因为n最大不超过100万，根据程序输出发现10！超过100万了，所以阶乘的范围是0！~9！
//将0~9的阶乘放在动态数组里；将所有阶乘和的可能性放在一个集合里，
//根据输入值判断，是否在集合里有一个数与n相等；若有，则输出YES；否则输出NO
 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main(){
	vector<int> jc;//存放0~9的阶乘 
	int i,cursum=1;
	jc.push_back(1);
	for(i=1;i<10;++i){
		cursum=cursum*i;//计算每个数的阶乘，并把他们放进jc数组里 
		jc.push_back(cursum);
		
	}
	//输出0~9的阶乘 
//	for(i=0;i<10;++i){
//		printf("%d:%d\n",i,jc[i]);
//	}
//计算所有阶乘和的可能性
    
    set<int> allPossible;
    allPossible.insert(0);
    set<int> tempSet;//将allPossible加上下一个阶乘后的集合放进tempSet集合中 
	set<int>::iterator it;
	for(i=0;i<10;++i){ //所有阶乘加or不加 
		 for(it=allPossible.begin();it!=allPossible.end();++it){
		 	tempSet.insert(*it+jc[i]);
		 }
	      for(it=tempSet.begin();it!=tempSet.end();++it){
 	        allPossible.insert(*it);//将加上下一个阶乘后的集合并入allPossible 
	}		 
	}

	allPossible.erase(0);
	
	int n;
	while(scanf("%d",&n)!=EOF){
		if(n<0){
			break;
		}
		if(allPossible.count(n)!=0){
			printf("YES\n");
		}
		else{
			printf("NO\n");
		}
	}
	
	return 0;
}