各桁の合計が指定した値と等しい数の個数を求めるアルゴリズム

概要

n 桁の整数のうち、各桁の数字の合計が指定された値と一致するものがいくつ存在するかを求める問題です。ここでは「0 は桁として数えない」、すなわち数の先頭を 0 にできないというルールが適用されます。たとえば 3 桁の数であれば、百の位には 1〜9 のいずれかの数字しか使えません。

制約は次のとおりです。

• 桁数 n：1 以上 100 以下
• 合計値：1 以上 500 以下

入力と出力

入力：
アルゴリズムは桁数と合計値を受け取ります。
ここでは、桁数を 3、合計を 15 とします。
出力：
各桁の合計が 15 となる異なる 3 桁の数の個数を表示します。
結果は 69 です（合計が 15 になる 3 桁の数は全部で 69 個あります）。

アルゴリズム

すべての組み合わせを素朴に列挙すると、桁数が増えるにつれて計算量が指数関数的に増大してしまいます。そこでメモ化再帰（動的計画法）を用います。「残りの桁数」と「残りの合計」の組み合わせごとに答えを表にキャッシュすれば、同じ部分問題を何度も計算する必要がなくなります。

count(digit, sum)

入力： 残りの桁数、残りの合計値
出力： 条件を満たす数の個数

Begin
    if digit = 0, then
        return true when sum = 0

    if memTable[digit, sum] is not vacant, then
        return memTable[digit, sum]
    answer := 0

    for i := 0 to 9 do
        if sum - i >= 0, then
            answer := answer + count(digit - 1, sum - i)
    done

    return memTable[digit, sum] := answer
End

digit が 0 になった時点で、sum もちょうど 0 になっていれば有効な数が 1 つ見つかったことになり、そうでなければ 0 を返します。現在の桁に 0〜9 の各数字を当てはめながら再帰的に数え上げ、結果を memTable に保存して以後の参照に備えます。

numberCount(digit, sum)

入力： 桁数、合計値
出力： 条件を満たす数の総個数

Begin
    define memTable and make all space vacant
    res := 0

    for i := 1 to 9, do
        if sum - i >= 0, then
            res := res + count(digit - 1, sum - i)
    done

    return result
End

先頭の桁には 0 を使えないため、最初の 1 桁だけは 1〜9 の範囲から選びます。残りの桁については count() に処理を委ねます。

C++ による実装例

#include<iostream>
#define ROW 101
#define COL 501
using namespace std;

unsigned long long int memTable[ROW][COL];

// 残り digit 桁で合計 sum を作る場合の数を返す
unsigned long long int count(int digit, int sum) {
    if (digit == 0)   // 桁を使い切ったら、合計が 0 かどうかを確認
        return sum == 0;

    if (memTable[digit][sum] != -1)   // 部分問題の答えが既にあればそれを返す
        return memTable[digit][sum];

    unsigned long long int ans = 0;   // 初回は答えを 0 に初期化

    for (int i = 0; i < 10; i++)   // 各数字について、それで始まる数を数える
        if (sum - i >= 0)
            ans += count(digit - 1, sum - i);
    return memTable[digit][sum] = ans;
}

unsigned long long int numberCount(int digit, int sum) {
    for (int i = 0; i < ROW; i++)   // メモ化テーブルをすべて -1 で初期化
        for (int j = 0; j < COL; j++)
            memTable[i][j] = -1;

    unsigned long long int result = 0;
    for (int i = 1; i <= 9; i++)   // 先頭の桁は 1〜9 から選ぶ
        if (sum - i >= 0)
            result += count(digit - 1, sum - i);
    return result;
}

int main() {
    int digit, sum;
    cout << "Enter digit count: "; cin >> digit;
    cout << "Enter Sum: "; cin >> sum;
    cout << "Number of values: " << numberCount(digit, sum);
}

memTable のサイズは、最大で 100 桁・合計 500 の入力に対応できるよう 101×501 として確保しています。初期化時にすべての要素を -1（未計算の印）で埋め、一度計算した値は即座に再利用します。また、答えが非常に大きな値になる可能性があるため、オーバーフローを避けるために unsigned long long int 型を使用しています。

出力

Enter digit count: 3
Enter Sum: 15
Number of values: 69

このように、桁数 3・合計 15 を入力すると、条件を満たす数が 69 個であることが分かります。メモ化によって重複する計画が排除されるため、桁数 100・合計 500 といった大きな入力でも高速に処理できます。