aoj0030:Sum of Integers

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030

解法

0~9までのそれぞれに対して足すか足さないかを全探索。その結果条件を満たしていれば数える。足すか足さないかでそれぞれ2通りあるので的な感じになる。再帰を用いると楽。（十重ループでも解けそう）

コード

#include<bits/stdc++.h>
using namespace std;

int n,s;
int dfs(int p,int t,int r){
    if(p==10){
        if(t==0&&r==s)return 1;
        return 0;
    }
    return dfs(p+1,t,r)+dfs(p+1,t-1,r+p);
}
int main(){
    while(cin>>n>>s,n||s)cout<<dfs(0,n,0)<<endl;
    return 0;
}