20180925

写一个程序is_additive(s)，判断一个字符串是不是加和序列。 如果一个字符串是一个加和序列，那么字符串可以被拆分成为这样一个序列，序列的相邻两项和等于下一项。

输入 : s = “235813”
输出 : true
2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13
输入 : s = “199100199”
输出 : true
1 + 99 = 100, 99 + 100 = 199
输入 : s = “12345678”
输出 : false

答案： 还是决策树模型，p代表决策，p中每一项都是从左侧选中的数字。

function is_additive(s, p = []) {
  if(s.length === 0) {
    return p.length >= 3
  }

  // 递归体循环递归每种取字符的情况
  for(let i = 1; i <= s.length; i++) {
    const v = parseInt( s.slice(0, i) )
    const tail = s.slice(i)
    if (
      p.length < 2 || (
        p.length >= 2 &&
        p[p.length - 1] + p[p.length - 2] === v
      )
    ) { 
      if (is_additive(tail, decisions.concat(v))) {
        return true
      }
    }
  }
  return false
}