はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

Volume0-0030 Sum of Integers

問題
整数の和 | Aizu Online Judge

与えられた整数sを、0~9の数字のうちn個の和で表す時の場合の数を求める問題です。
全探索すれば良いのですが、今まで全探索のプログラムを書いたことがなかったので、かなり苦戦しました。

#include<stdio.h>
 
int A[11]={0,1,2,3,4,5,6,7,8,9,0};
int cnt=0;
 
void dfs(int i,int rest,int d,int n){
 
 if(i<11){
    if(d==n){
      if(rest==0){cnt++;return;}
      else return;
    }
 
    if(rest<0)return;/*sを超える*/
 
    dfs(i+1,rest-A[i],d+1,n);/*A[i]を選ぶ*/
    dfs(i+1,rest,d,n);/*A[i]を選ばない*/
 
 }
 
return;
}
 
 
 
 
int main(){
 int n,s;
 
 while(1){
 
      scanf("%d %d",&n,&s);
      if(n==0 && s==0)break;
      if(s > 55)printf("0\n");
      else {
            cnt=0;
            dfs(0,s,0,n);
            printf("%d\n",cnt);
 
      }
 }
 
 return 0;
}

全探索、もっと練習します。