本文共 1463 字，大约阅读时间需要 4 分钟。

描述

给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！+2!+3!，如果是，则输出Yes，否则输出No；

输入

第一行有一个整数0<m<100,表示有m组测试数据；

每组测试数据有一个正整数n<1000000;

输出

如果符合条件，输出Yes，否则输出No;

样例输入

2910

样例输出

Yes

No

思路一：搜索

注意这个dfs的理解：每一层调用下一层时候，调用层的值由下面两层决定，根据dfs特点，下一层有正确的上面调用层的值就为true（看成一个普通的函数调用其它两个函数,正确即返回true）

依次类推，在到达搜索最底层的时候，如果最底层有一个是正确的则总的结果就是正确的，即有组合满足阶乘和为n。

这个算法的复杂度很高O（2^n）每层两种情况，直到底层进行判断.

#include
   
    using namespace std;int t,n;int f[12];int fac(int n){	if(n == 0 || n == 1)		return 1;	else return n*fac(n-1);}bool dfs(int p,int sum){	if(p == 12){		return sum == n;	}	if(dfs(p+1,sum+f[p]))		return true;	if(dfs(p+1,sum))		return true;	return false;}int main()	{		for(int i = 1; i < 12; ++i){			f[i] = fac(i); 		}		scanf("%d",&t);		while(t--){			scanf("%d",&n);			if(dfs(1,0)){				printf("Yes\n");			}			else{				printf("No\n");			}			}					return 0;		}
   

思路二 贪心：

其实贪心对于此类问题并不是都对，只是在这种情况下是对的

例如 抛开此题，问给定N 是否是，某些数中的一些数的和

9

1 3 6 7

此时按照这种逻辑 是判断为No的，但是事实上3+6 = 9是可以的

我认为此种方法正确的必要条件是这些数为不同的数量级（当然有些是同一数量级，但是不会形成上述的那种情形）

等 知道具体原理 再来改写。。。

#include
   
    using namespace std;int t,n;int f[12];int fac(int n){	if(n == 0 || n == 1)		return 1;	else return n*fac(n-1);}int main()	{		for(int i = 1; i < 12; ++i){			f[i] = fac(i); 		}		scanf("%d",&t);		while(t--){			scanf("%d",&n);			for(int i = 9; i > 0; --i){//从大数开始，依次比较可以就减去				if(n >= f[i])					n -= f[i];			}			if(n == 0){				printf("Yes\n");			}			else{				printf("No\n");			}			}					return 0;		}
   

转载地址：http://ueimi.baihongyu.com/