５問目（組み合わせ・再帰）

問題

0～9の数字から異なるn個の数を取りだし、その合計がsとなる組み合わせの数を出力して終了するプログラム。

たとえば、nが3で、sが5のときは
0+1+4 = 5
0+2+3 = 5
の２通りとなります。

入力

n（整数）
s（整数）

出力

nこの整数の我がsになる組み合わせの数（整数）

入力例

3
5

出力例

2

解き方例

組み合わせ生成です。方法はいくつかありますが、再帰を使ってみましょう。

ソースコード

お持ち帰り

C/C++

#include <stdio.h>

int g_n;
int g_count=0;
int g_s;

void func(int n,int s,int sum){
    int i;
    if(n==g_n){
        if(sum==g_s)g_count++;
    }

    for(i=s;i<10;i++){
        func(n+1,i+1,sum+i);
    }
}

int main(){
    scanf("%d",&g_n);
    scanf("%d",&g_s);

    func(0,0,0);

    printf("%d",g_count);

    return 0;
}

その他

コードを読めば分かりますが、結構効率の悪いコードです。でも、書きやすいコードです。