AOJ 0030 c

AOJの0030、入力した合計になるような足し算の組み合わせの数を出力する問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030




正直全然わからなかったので調べてみると、どうやら深さ優先探索（Depth First Search）なることをするようです。ここでiは足す数、sは現在の合計（Sumが最終目標の合計）、nがあと何回足すかを表しています。

dfs(i+1,s+i,n-1); //1
dfs(i+1,s,n); //2

この分岐にそれぞれ①②と番号をふったとすると、
①は足し算で②は場合分けの方向に分かれています。
画像はその時のメモです。（分かりづらい上にきたない…）

メモ中の数字はiで、
s == Sum かつ n == 0となれば、ひとつの組み合わせが見つかったので答えにカウントされます。

参考サイト（http://d.hatena.ne.jp/print7/20111004/1317697039）

以下、提出したソースコードです。

#include <stdio.h>

int ans,Sum;

void dfs(int i,int s,int n)
{
    if(s == Sum && n == 0)
    {
        ans++;
        return;
    }

    if(i == 10 || n == 0)
        return;

    dfs(i+1,s+i,n-1);
    dfs(i+1,s,n);
}

int main(void)
{
    int n;

    while(scanf("%d %d",&n,&Sum) != EOF)
    {
        if (n == 0 && Sum == 0)
            break;

        ans = 0;
        dfs(0,0,n);

        printf("%d\n", ans);
    }

    return 0;
}