C++で加算数（Additive Number）を判定する方法｜再帰と全探索による実装

加算数（Additive Number）とは？

「0」から「9」までの数字のみで構成された文字列が与えられたとき、その文字列が加算数（Additive Number）であるかどうかを判定する関数を作成することを考えます。

加算数とは、文字列の桁をいくつかの数に分割したときに加算列（Additive Sequence）を形成できる文字列のことです。有効な加算列には少なくとも3つの数が含まれ、最初の2つの数を除き、列の中の後続の各数は必ず直前の2つの数の和と一致しなければなりません。

たとえば、入力が「112358」の場合、以下のように分解できるため、答えは true になります。

• 2 = 1 + 1
• 3 = 1 + 2
• 5 = 2 + 3
• 8 = 3 + 5

解法のアプローチ

この問題は、先頭の2つの数の切り分け方を全探索し、残りの部分が条件を満たすかを再帰的に確認する方針で解くことができます。手順は以下の通りです。

• ok() メソッドを定義する。引数は文字列 s、開始位置 index、直前の2つの数 prev1 と prev2 です。
• index が s の長さ以上であれば true を返します（文字列の末尾まで到達できた＝加算列が成立）。
• req := prev1 + prev2 とし、num を req を文字列に変換したものとします。
• x を空文字列で初期化します。
• i を index から s の末尾までループします。
  • x に s[i] を1文字ずつ追加します。
  • x が num と一致し、かつ ok(s, i + 1, prev2, x を整数化した値) が true を返す場合は true を返します。
• いずれの分割でも成立しなければ false を返します。

メインメソッド側では以下の手順を実行します。

• n を num の長さとします。
• i を 1 から n − 2 まで、さらに j を 1 から i まで二重ループで回します。
  • s1 を num の先頭から j 文字分、s2 をその直後から i 番目までの部分文字列とします。
  • x を s1 と s2 の長さの大きい方とします。
  • x が n − i より大きい場合、残りの文字数が不足するため次の反復へ進みます。
  • s1 または s2 が「0」で始まる複数桁の数（先行ゼロを含む不正な表現）である場合はスキップします。
  • ok(num, i + 1, s1 を整数化した値, s2 を整数化した値) が true を返せば、true を返します。
• すべての組み合わせで成立しなければ false を返します。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool ok(string s, int idx, lli prev1, lli prev2){
        if(idx >= s.size()) return true;
        lli req = prev1 + prev2;
        string num = to_string(req);
        string x = "";
        for(int i = idx; i < s.size(); i++){
            x += s[i];
            if(x == num && ok(s, i + 1, prev2, stol(x))) return true;
        }
        return false;
    }
    bool isAdditiveNumber(string num) {
        int n = num.size();
        for(int i = 1; i < n - 1; i++){
            for(int j = 1; j <= i; j++){
                string s1 = num.substr(0, j);
                string s2 = num.substr(j, i - j + 1);
                int x = max((int)s1.size(), (int)s2.size());
                if(x > n - i) continue;
                if((s1[0] == '0' && s1.size() > 1) || (s2[0] == '0' && s2.size() > 1)) continue;
                if(ok(num, i + 1, stol(s1), stol(s2))) return true;
            }
        }
        return false;
    }
};
main(){
    Solution ob;
    cout << (ob.isAdditiveNumber("112358"));
}

入力

"112358"

出力

1

補足：計算量と実装上のポイント

先頭2つの数の分割位置の組み合わせは最大で O(n²) 通り存在し、それぞれに対して再帰的な検証が行われます。ただし、一度2つの数が確定すると、次の数の桁数はほぼ一意に決まるため、探索範囲は実際にはすぐに絞り込まれます。

また、大きな入力に対応できるよう long long int 型を使用してオーバーフローを回避している点や、「0」で始まる複数桁の数を不正な表現として除外している点も、この実装における重要なポイントです。