如何使用递归获取JavaScript数组的任意长度元素所有组合

解法思路 #

你需要实现的是生成数组的所有子集（幂集），每个元素都有「纳入组合」和「不纳入组合」两种可能，递归时把这两种分支都覆盖就能得到全部无重复的组合。

修改后代码 #

function getAllCombos(arr) {
  // 递归终止条件：空数组的子集只有自身
  if (arr.length === 0) return [[]]
  // 取当前数组第一个元素
  const first = arr[0]
  // 递归得到剩余元素的所有子集
  const restCombos = getAllCombos(arr.slice(1))
  // 合并两种情况：1、包含第一个元素的子集（把first拼到剩余元素的每个子集前）；2、不包含第一个元素的子集（就是剩余元素的子集本身）
  return [...restCombos.map(combo => [first, ...combo]), ...restCombos]
}

运行测试 #

测试你给出的用例：

console.log(getAllCombos(['a', 'b']))
// 输出：[['a','b'], ['a'], ['b'], []]
console.log(getAllCombos(['a', 'b', 'c']))
// 输出：[['a','b','c'],['a','b'],['a','c'],['a'],['b','c'],['b'],['c'],[]]

和你期望的结果完全匹配，因为每个元素的选择分支互斥，天然不会生成重复组合。

内容的提问来源于stack exchange，提问作者peiwei333