leetcode 306. 累加数高精度加法+回溯

 1 class Solution {
 2 public:
 3     vector<string>ans;
 4     bool isAdditiveNumber(string num) {
 5         int n=num.size();
 6         function<int(int,int)>dfs=[&](int u,int k)
 7         {
 8               if(k>=3)
 9             {
10                 string s1=ans[k-3],s2=ans[k-2],s3=ans[k-1];
11                 int n1=s1.size(),n2=s2.size(),jw=0;
12                 int p1=n1-1,p2=n2-1;
13                 string ans="";
14                 while(p1>=0||p2>=0)
15                 {
16                     int t=((p1>=0)?(s1[p1--]-'0'):0) +((p2>=0)?(s2[p2--]-'0'):0)+jw;
17                     jw=t/10;
18                     ans.push_back(char(t%10+'0'));
19                     
20                 }
21                 if(jw)ans.push_back('1');
22                 reverse(ans.begin(),ans.end());
23                 if(ans!=s3)return 0;
24             }
25             if(u==n)
26             {
27                 if(k>=3)return 1;
28                 else return 0;
29             }
30             for(int i=1;u+i-1)
31             {
32                 if(i>1&&num[u]=='0')continue;
33                 ans.push_back(num.substr(u,i));
34                 if(dfs(u+i,k+1))return 1;
35                 ans.pop_back();
36             }
37             return 0;
38         };
39         return dfs(0,0);
40     }
41 };