题目

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1:输入: "112358" 输出: true

解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:输入: "199100199" 输出: true

解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

进阶:你如何处理一个溢出的过大的整数输入?

解题思路分析

1、回溯；时间复杂度O(n(log(n))^2)，空间复杂度O(n)

var res []intfunc isAdditiveNumber(num string) bool {if len(num) < 3 {return false}res = make([]int, 0)dfs(num, 0, 0, 0, make([]int, 0))return len(res) >= 3}func dfs(s string, index, sum, prev int, path []int) bool {if index == len(s) {if len(path) >= 3 {res = path}return len(path) >= 3}value := 0for i := index; i < len(s); i++ {// 0开头不满足要求(当前i=index的时候，可以为0， 避免错过1+0=1的情况)if s[index] == '0' && i > index {break}value = value*10 + int(s[i]-'0')if len(path) >= 2 {if value < sum {continue}if value > sum {break}}if dfs(s, i+1, prev+value, value, append(path, value)) == true {return true}}return false}

总结

Medium题目，回溯问题，题目类似leetcode 842.将数组拆分成斐波那契序列