地址 https://www.papamelon.com/problem/194
解答
书本的第一个例题 直接暴力吧
由于抽签是拿出来再放进去袋子 重新抽,也就是选择数字可以重复
那么每次选择数字的范围都是0~~n 四重循环 时间复杂度就是O(n^4)
#include <iostream>
using namespace std;
const int N =100;
int arr[N];
int n,m;
int main(){
cin >>n>>m;
for(int i = 0;i < n;i++) cin >> arr[i];
for(int i = 0;i < n;i++){
for(int j =0;j<n;j++){
for(int k = 0;k<n;k++){
for(int l =0;l<n;l++){
if(arr[i]+arr[j]+arr[k]+arr[l] == m){
cout << "Yes"<<endl; return 0;
}
}
}
}
}
cout << "No" <<endl;
return 0;
}
也可以使用DFS 遍历各种4个数字的组合,查看是否能够得到要求的和。
#include <iostream>
using namespace std;
const int N = 100;
int arr[N];
int n,m,sum,flag ;
void dfs(int idx){
if(idx==4){
if(sum == m){ flag =1;}
return;
}
if(1==flag){return;}
for(int i =0;i < n;i++){
//尝试加上该数
sum += arr[i];
dfs(idx+1);
//还原 以便继续下一次尝试
sum -= arr[i];
}
return;
}
int main(){
cin >> n >>m;
for(int i = 0;i <n;i++){cin>>arr[i];}
dfs(0);
if(flag==1){ cout << "Yes"<<endl;}
else{ cout << "No" << endl;}
return 0;
}