読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

aoj0030:Sum of Integers

解法

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

コード

#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;
}