我要评论ZJYYCOJ问题 B: 组数总和
题目描述
LZY今天又突发奇想了，他想随意给出两个数字n和k，请你找出所有N个数字相加和为K的组合数量。组合中只含有1——9的数字，并且不允许重复。
输入格式：
测试样例由多组测试数据组成。每组测试样例第一行输入两个正整数n ( 1 <= n <= 9 ） 和 k < ( 1 <= k <= 45 ）。
输出格式：
仅一个整数，表示最少要穿过多少次圆的边界。
样例输入 Copy
3 7
3 9
样例输出 Copy
1
3
思路
这题的话是我做过的dfs中的第二题，这题的话思路还是蛮清楚的，就是从大到小的dfs算出sum的值进行比较。
AC代码
#include<bits/stdc++.h>
using namespace std;
int vis[15] = {0};
int n,k;
int sum = 0;
int ans = 0;
void dfs(int len ,int k,int j){
if(len == n && sum == k){
ans ++;
return;
}
else if(sum > k){
return;
}
else if(len == n && sum != k){
return;
}
for(int i = j ; i <= 9 ; i ++){
if(vis[i] == 0){
sum += i;
vis[i] = 1;
dfs(len + 1 , k , i);
}
else{
continue;
}
vis[i] = 0;
sum -= i;
}
}
int main(){
while(cin >> n >> k){
ans = 0;
dfs(0,k,1);
if(ans != 0){
cout << ans << endl;
}
else{
cout << "No list" << endl;
}
}
}
本文地址：https://blog.csdn.net/weixin_46323249/article/details/108579696
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论