C ++中的加数
为了解决这个问题，我们将遵循以下步骤-
定义一个名为的方法ok()，它将采用s，index，prev1，prev2
如果索引>=s的大小，则返回true
req：=prev1+prev2和num：=req作为字符串
x：=一个空白字符串
对于i在s大小的范围索引中
x：=x+s[i]
如果x=num，并且ok（s，i+1，prev2，x为整数），则返回true
返回假
从主要方法中执行以下操作-
n：=num的大小
当我在1到n–2的范围内时
s1：=num的子串，从0到j–1
s2：=从j到i–num的子字符串
x：=s1大小和s2大小的最大值
如果x>n–i，则进行下一次迭代
如果（s1[0]为0且s1的大小>0）或（s2[0]为0且s2的大小>1），则跳至下一个迭代
如果ok（num，i+1，s1为整数，s2为整数）为true，则返回true
对于1到i范围内的j
返回假
例子（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