306. 累加数

原题链接：LeetCode 306. 累加数

题目描述

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

一个有效的 累加序列 必须** 至少 **包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

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

示例 1：

"112358"

示例 2：

：

提示：

- `1 <= num.length <= 35`

- `num` 仅由数字（`0` - `9`）组成

**进阶：**你计划如何处理由过大的整数输入导致的溢出?

难度： Medium

题解代码

javascript

/**
 * @param {string} num
 * @return {boolean}
 */
let is = false
var isAdditiveNumber = function(num) {
  if (num.length < 3) return false
  is = false
  backTrack(num, [])
  return is
};

function backTrack (s, path) {
  if (!s.length && isValid(path) && path.length >= 3) {
    is = true
    return
  }
  for (let i = 1; i < s.length + 1; i++) {
    const item = s.slice(0, i)
    if (item[0] === '0' && item.length > 1) continue
    const temp = [...path].slice(path.length - 2)
    temp.push(item)
    if (!isValid(temp)) continue
    path.push(item)
    s = s.slice(i)
    backTrack(s, path)
    s = path.pop() + s
  }
}

function isValid (arr) {
  for (let i = 2; i < arr.length; i++) {
    if (parseInt(arr[i]) !== (parseInt(arr[i - 1]) + parseInt(arr[i - 2]))) {
      return false
    } 
  }
  return true
}

306. 累加数 #

题目描述 #

题解代码 #

306. 累加数

题目描述

题解代码