其它回溯篇 ​

const partition = s => {
  const [ret, len] = [[], s.length]
  const pali = Array(len)

  for (let i = 0; i < len; i++) {
    pali[i] = Array(len)
  }

  const isPali = (s, l, r) => {
    while (l < r) {
      if (s[l] !== s[r]) {
        pali[l][r] = false
        return false
      }
      l++
      r--
    }
    pali[l][r] = true
    return true
  }

  const dfs = (path, idx) => {
    // 指针越界了，没有可以切分的子串了
    // 递归到这一步，说明一直在切出回文串，现在生成了一个合法的部分解
    if (idx === len) {
      ret.push([...path])
      return
    }
    for (let i = idx; i < len; i++) {
      if (pali[idx, i] === false) continue
      if (pali[idx][i] || isPali(s, idx, i)) {
        path.push(s.substring(idx, i + 1))
        dfs(path, i + 1)
        path.pop()
      }
    }
  }
  dfs([], 0)
  return ret
}

const generateParenthesis = n => {
  const ret = []
  const dfs = (path, l, r) => {
    // 字符串构建完成
    if (path.length === 2 * n) {
      ret.push(path)
      return
    }
    // 只要 ( 有剩，就优先选 (
    if (l > 0) dfs(path + '(', l - 1, r)
    // ) 剩的比 ( 多，才能选 )
    if (r > l) dfs(path + ')', l, r - 1)
  }
  dfs('', n, n)
  return ret
}

const restoreIpAddresses = s => {
  const [ret, len] = [[], s.length]

  const dfs = (path, idx) => {
    // 片段满4段，且耗尽所有字符
    if (path.length === 4 && idx === len) {
      ret.push(path.join('.'))
      return
    }
    // 满4段，字符未耗尽，不用往下选了
    if (path.length === 4 && idx < len) return

    for (let i = 1; i < 4; i++) {  // 枚举出选择，每段三种切割长度
      if (idx + i - 1 >= len) return  // 加上要切的长度就越界，不能切这个长度
      if (i !== 1 && s[idx] === '0') return  // 不能切出'0x'、'0xx'
      const str = s.substring(idx, idx + i)
      if (i === 3 && +str > 255) return  // 当前切出的片段不能超过255
      path.push(str)
      dfs(path, idx + i)
      path.pop()
    }
  }
  dfs([], 0)
  return ret
}