C++での加算数

これを解決するには、次の手順に従います-

• ok（）というメソッドを定義します。これには、s、index、prev1、prev2が必要です

  。

• index> =sのサイズの場合、trueを返します

• req：=prev1 + prev2およびnum：=req as string

• x：=1つの空白の文字列

• 範囲インデックスからsのサイズまでのiの場合

  • x：=x + s [i]

  • x =numで、ok（s、i + 1、prev2、x as integer）の場合、trueを返します

• falseを返す

• メインの方法から、次のようにします-

• n：=numのサイズ

• 1からn–2の範囲のiの場合

  • 1からiの範囲のjの場合

    • s1：=0からj–1までのnumの部分文字列

    • s2：=jからiまでのnumの部分文字列– j

    • x：=s1サイズとs2サイズの最大値

    • x> n – iの場合、次の反復に進みます

    • （s1 [0]が0で、サイズがs1> 0）または（s2 [0]が0で、サイズがs2> 1）の場合、次の反復にスキップします

    • ok（num、i + 1、s1 as integer and s2 as integer）が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