因子组合如何用回溯枚举？为什么递归要限制起始因子？

简化版

因子组合要求把一个数拆成多个大于 1 的因子相乘。

回溯时从某个起始因子 start 开始枚举，只尝试能整除当前剩余值 remain 的因子。

为了避免 [2,6] 和 [6,2] 重复，下一层仍从当前因子开始枚举，保证路径非递减。

详细版

递归状态可以定义为：当前剩余乘积 remain，下一次可选因子的最小值 start，当前路径 path。

每次枚举 factor 从 start 到 sqrt(remain)：

如果 remain % factor !== 0，跳过；
否则可以选择 factor；
此时 remain / factor 也可以作为路径最后一个因子形成答案；
也可以继续递归拆分 remain / factor。

限制起始因子能让组合按非递减顺序生成，避免排列重复。

完整版教学

一、为什么需要限制顺序

因子组合是组合问题，不是排列问题。[2,6] 和 [6,2] 表示同一种拆法，都等于 12。如果每层都从 2 开始枚举，就会生成不同顺序的重复结果。限制下一层因子不小于当前因子，可以让每个组合按非递减顺序出现。

记忆钩子：组合去重常靠 start；因子组合的 start 表示最小可选因子。

二、递归状态怎么定义

remain 表示还需要被拆解的剩余乘积。start 表示当前层允许选择的最小因子。path 是已经选好的因子列表。每当找到一个 factor 能整除 remain，就说明可以把它加入路径。

状态	含义	示例
`remain`	待拆的数	12
`start`	最小候选因子	2
`path`	已选因子	[2]

这些状态共同保证不重复、不漏解。

三、为什么枚举到 sqrt(remain)

如果 factor > sqrt(remain)，那么与它配对的另一个因子一定小于 sqrt(remain)，此前已经被枚举过。比如 remain = 36，因子对是 (2,18)、(3,12)、(4,9)、(6,6)，超过 6 的左因子会重复。

只枚举小因子
大因子通过 remain / factor 得到

这样能减少搜索范围。

四、代码模板

实现如下：

function getFactors(n) {
  const ans = []
  const path = []

  function dfs(remain, start) {
    for (let f = start; f * f <= remain; f++) {
      if (remain % f !== 0) continue
      path.push(f)
      ans.push([...path, remain / f])
      dfs(remain / f, f)
      path.pop()
    }
  }

  dfs(n, 2)
  return ans
}

ans.push([...path, remain / f]) 表示当前因子加上剩余大因子已经构成一个完整组合。

五、带数字推演

以 n = 16 为例：

选 2 -> 剩 8 -> 得到 [2,8]
继续选 2 -> 剩 4 -> 得到 [2,2,4]
继续选 2 -> 剩 2，停止
回到剩 8，选 4 不满足 f*f<=8，停止
选 4 -> 剩 4 -> 得到 [4,4]

最终组合有 [2,8]、[2,2,4]、[2,2,2,2]、[4,4]。

六、常见误区与追问

误区：每层从 2 开始枚举。 会生成不同顺序的重复组合。
误区：把 n 本身作为单独组合。 通常题目要求至少两个因子，[n] 不算。
误区：枚举到 remain。 可以但效率低，枚举到平方根就够。
追问：为什么可以加入 remain/factor？ 因为它和当前 path 的乘积已经等于原目标。
追问：质数输入怎么办？ 没有可拆因子，返回空数组。

这些点考的是组合去重和因子对关系。

七、加强记忆

因子组合记成“路径非递减，枚举到根号，剩余因子直接收”。start 防止 [2,6] 和 [6,2] 重复；remain 表示还要拆的部分；每找到一个小因子，就能把大因子 remain/f 和路径组成答案，也能继续往下拆。质数自然没有分支。

简化版

详细版