问题描述
小R不再追求甜点中最高的喜爱值，今天他想要的是甜点喜爱值之和正好匹配他的预期值 S。为了达到这个目标，他可以使用魔法棒来改变甜点的喜爱值，使其变为原来喜爱值的阶乘。每个甜点只能使用一次魔法棒，也可以完全不用。
下午茶小哥今天带来了 N 个甜点，每个甜点都有一个固定的喜爱值。小R有 M 个魔法棒，他可以选择任意甜点使用，但每个甜点只能使用一次魔法棒。他的目标是通过选择一些甜点，可能使用魔法棒，使得这些甜点的喜爱值之和恰好为 S。
请计算小R有多少种不同的方案满足他的要求。如果两种方案中，选择的甜点不同，或者使用魔法棒的甜点不同，则视为不同的方案。
测试样例
样例1：
输入：
n = 3, m = 2, s = 6, like = [1, 2, 3]
输出：5
样例2：
输入：
n = 3, m = 1, s = 1, like = [1, 1, 1]
输出：6
样例3：
输入：
n = 5, m = 3, s = 24, like = [1, 2, 3, 4, 5]
输出：1
样例4：
输入：
n = 4, m = 0, s = 10, like = [1, 3, 3, 3]
输出：1
样例5：
输入：
n = 6, m = 1, s = 35, like = [5, 5, 5, 5, 5, 5]
输出：0
题解：
对于数组like中任意一个元素，有四种选择：选择，不选，用魔法棒选，用魔法棒不选。但是题目说明不能用魔法棒但不选，所以只有三种方式。直接暴力DFS即可。
再说一下退出条件，当满足条件返回，所有元素遍历完返回，魔法棒用完返回，以及所选value>s返回。
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long ll;
int sum=0;
ll jie(int x){
int i=0;
ll sum=1;
for(i=1;i<=x;i++){
sum*=i;
}
return sum;
}
void dfs(int i,int n,int m,int s,vector<int> like){
//cout << i << " " << n << " " << m << " " << s << "\n";
if(s==0 && m>=0 && i<=n){
sum++;
//cout << "YES " << i << "\n";
return;
}
if(s<0){
//cout << "1"<<"\n";
return;
}
if(m<0){
//cout << "2" << "\n";
return;
}
if(i==n){
//cout << "3" << "\n";
return;
}
//不用但选
dfs(i+1,n,m,s-like[i],like);
//不用不选
dfs(i+1,n,m,s,like);
//用不选
//dfs(i+1,n,m-1,s,like);
//用选
dfs(i+1,n,m-1,s-jie(like[i]),like);
}
int solution(int n, int m, int s, std::vector<int> like) {
sum=0;
// Please write your code here
dfs(0,n,m,s,like);
//cout << sum << "\n";
return sum;
}
int main() {
// You can add more test cases here
std::vector<int> like1 = {1, 2, 3};
std::vector<int> like2 = {1, 1, 1};
std::cout << (solution(3, 2, 6, like1) == 5) << std::endl;
std::cout << (solution(3, 1, 1, like2) == 6) << std::endl;
return 0;
}