悬赏 epic的OA一道题 additive number

感谢指点！

有大神说下思路吗。。。

1. #include <vector>
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. class Solution{
   
7. public:
   
8.         vector<int> additiveNum(int start, int end){
   
9.                 vector<int> ret;                                                       
   
10.                 for(int i = start; i <= end; i++)
    
11.                         if(isAdditive(i))
    
12.                                 ret.push_back(i);
    
13.                 return ret;
    
14.         }
    
15. 
    
16.         bool isAdditive(int num){
    
17.                 string s = to_string(num);
    
18.                 if(s.length() < 3) return false;
    
19.                 for(int i = 2; i/2 <= s.length()-i; i++){        // i== length of sum of two first string
    
20.                         for(int j = 1; j <= i-1; j++){                        // j== length of first string
    
21.                                 string s1 = s.substr(0,j);                        // s1: 0,j-1; s2: j,i-1
    
22.                                 string s2 = s.substr(j,i-j);
    
23.                                 if(s1[0]=='0' || s2[0]=='0') break;        // 0XX is not allowed
    
24.                                 int i1 = stoi(s1);
    
25.                                 int i2 = stoi(s2);
    
26.                                 int i3 = i1+i2;
    
27.                                 string s3 = to_string(i3);
    
28.                                 if(s.find(s3) != i) break;
    
29.                                 if(helper(s2,s3,s.substr(j))) return true;
    
30.                         }
    
31.                 }
    
32.                 return false;
    
33.         }
    
34. 
    
35.         bool helper(string s1, string s2, string s){
    
36.                 if(s.compare(s1+s2)==0) return true;
    
37.                 int i1 = stoi(s1); int i2 = stoi(s2);
    
38.                 int i3 = i1+i2;
    
39.                 string s3 = to_string(i3);
    
40.                 int pos = s1.length()+s2.length();
    
41.                 if(s.find(s3) != pos) return false;
    
42.                 else return helper(s2,s3,s.substr(s1.length()));
    
43.         }
    
44. };
    
45. 
    
46. int main(){
    
47.         Solution soln;
    
48.         vector<int> a = soln.additiveNum(10000,1000000);
    
49.         for(int i = 0; i < a.size(); i++)
    
50.                 cout<<a[i]<<endl;
    
51. }

复制代码

小弟不才 也贡献一个解答。
可能有corner case没有关注 欢迎指正，
效率似乎也不行，纯纯的brute force。。
不知此题有没有什么更快的方案。