题解 | #Sum of Factorials# 两种方法

• 分别使用暴力方法、dfs搜索可能的阶乘之和

#include <iostream>
using namespace std;
// 0~9的阶乘之和为 409,114，而 0~10阶乘之和为 4,037,914
void getFac(int *fac){ // 首先计算 0~9 阶乘
    fac[0]=1;
    for(int i=1;i<10;i++){
        fac[i]=fac[i-1]*i;
    }
}
// 1、暴力搜索 从大到小
bool check(int n,int *fac){ 
    for(int i=9;i>=0;i--){
        if(fac[i]<=n){ // 注意等号
            n-=fac[i];
        }
        if(n==0) return true;
    }
    return false;
}
// 2、使用 dfs 进行搜索 
bool checkInDFS(int n, int sum, int i, int *fac){
    // n为待判断的数, sum为当前已选过的阶乘之和, i为遍历深度
    // 从 0!到 9!，每层阶乘都有选和不选两种状态
    if(i==9){
        if(sum==n) return true;
        else return false;
    }
    // 若无法找到一种解，则本层结点选和不选的返回值都为 false
    if(checkInDFS(n, sum+fac[i], i+1, fac)||checkInDFS(n, sum, i+1, fac)) return true;
    else return false;
}

int main() {
    int fac[10];
    getFac(fac);
    int n;
    while(cin>>n){
        bool ans;
        ans=check(n,fac);
        // ans=checkInDFS(n,0,0,fac);
        if(ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}