回溯

• 回溯 = 递归 + 单重循环，和双重循环不一样
• 回溯：for 循环的每个选择都会递归进入下一层，形成树形搜索
• 双重循环：固定两层嵌套，所有循环在同一层次
• 时间复杂度通常是指数级或阶乘级（O(2^n) 或 O(n!)）

// 回溯通用模板
function backtrack(路径, 选择列表) {
  if (满足结束条件) {
    result.push(路径.slice()) // 注意要拷贝
    return
  }
  for (let 选择 of 选择列表) {
    做选择      // stack.push / remain -= val
    backtrack(路径, 选择列表)
    撤销选择    // stack.pop / remain += val
  }
}

题干：给定数字字符串（2-9），返回所有可能的字母组合。如 "23" → ["ad","ae","af","bd",...]

var letterCombinations = function (digits) {
  if (!digits) return []
  const map = new Map([
    [2, 'abc'], [3, 'def'], [4, 'ghi'], [5, 'jkl'],
    [6, 'mno'], [7, 'pqrs'], [8, 'tuv'], [9, 'wxyz'],
  ])
  let stack = []
  let ans = []

  const helper = (curIndex) => {
    if (curIndex === digits.length) {
      ans.push(stack.slice().join('')) // 收集结果
      return
    }
    let charArr = map.get(parseInt(digits[curIndex]))
    for (let i = 0; i < charArr.length; i++) {
      stack.push(charArr[i])   // 做选择
      helper(curIndex + 1)     // 递归下一层
      stack.pop()              // 撤销选择
    }
  }
  helper(0)
  return ans
}

题干：给定 n 对括号，生成所有合法的括号组合。

• 可加左括号条件：lRemain > 0
• 可加右括号条件：rRemain > lRemain（已用的左括号比右括号多）

var generateParenthesis = function(n) {
  let lRemain = n, rRemain = n
  let stack = []
  let ans = []

  const helper = (index) => {
    if (index === 2 * n) {
      ans.push(stack.slice().join(''))
      return
    }
    // 可以加左括号
    if (lRemain > 0) {
      stack.push('(')
      lRemain--
      helper(index + 1)
      stack.pop()
      lRemain++
    }
    // 可以加右括号（已用左括号比右括号多）
    if (rRemain > lRemain) {
      stack.push(')')
      rRemain--
      helper(index + 1)
      stack.pop()
      rRemain++
    }
  }
  helper(0)
  return ans
}

题干：从候选数组中找出所有和为 target 的组合，数字可以重复使用。

• 先排序，方便剪枝
• beginIndex 避免重复组合（只往后取，不回头）
• 递归传 i（而不是 i+1），允许重复选同一个数

var combinationSum = function(candidates, target) {
  candidates.sort((a, b) => a - b) // 排序方便剪枝
  let ansArr = []
  let curArr = []

  const helper = (remain, beginIndex) => {
    if (remain === 0) {
      ansArr.push(curArr.slice()) // 收集结果（注意拷贝）
      return
    }
    for (let i = beginIndex; i < candidates.length; i++) {
      let item = candidates[i]
      if (remain >= item) {
        curArr.push(item)      // 做选择
        remain -= item
        helper(remain, i)      // i 不是 i+1，允许重复
        remain += item         // 撤销选择
        curArr.pop()
      }
    }
  }
  helper(target, 0)
  return ansArr
}