306. 累加数（dfs回溯）

链接：306. 累加数

题解：

class Solution { public: bool isAdditiveNumber(string num) { if (num.size() <= 2) { return false; } int begin = 0; std::vector<uint64_t> path; return dfs(begin, num, path); } bool dfs(int begin, const std::string& num, std::vector<uint64_t>& path) { if (begin >= num.size() && path.size() >= 3) { cout << begin << endl; return true; } uint64_t sum = 0; for (int i = begin; i < num.size(); ++i) { sum = sum*10 + (num[i]-'0'); if (path.size() < 2) { path.push_back(sum); if (dfs(i+1, num, path)) { return true; } path.pop_back(); } else if (sum == path[path.size()-1] + path[path.size()-2]) { cout << sum << endl; path.push_back(sum); if (dfs(i+1, num, path)) { return true; } path.pop_back(); } if (num[begin] == '0') { break; } } return false; } };