能否将实现JavaScript数组所有子集的两个递归函数合并为一个？

我已经用两个递归函数实现了数组所有子集的生成，但想知道能不能把这两个递归逻辑整合到单个函数里。

习题任务 #

编写一个名为subsets的函数，返回数组的所有子集，示例如下：

• 输入[]，输出[[]]
• 输入[1]，输出[[], [1]]
• 输入[1,2]，输出[[], [1], [2], [1, 2]]
• 输入[1,2,3]，输出[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

提示 #

以subsets([1,2,3])为例，子集分为两类：

1. 不含3的子集（即[1,2]的所有子集）；
2. 每个不含3的子集添加3后得到的对应子集。

我的双递归实现代码 #

let arr = []
console.log(JSON.stringify(subsets(arr))); // [[]]
arr = [1]
console.log(JSON.stringify(subsets(arr))); // [[], [1]]
arr = [1,2]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

// your code here
function subsets(arr) {
  if (arr.length === 0) return [[]]; // base

  let el = arr.slice(-1)
  let prev = subsets(arr.slice(0, -1))
  return prev.concat(addEl(prev,el))
  //can be instead iterative: return prev.concat(prev.map(x => x.concat([el])));  
}

function addEl(arrA, el) {
  let firstEl = arrA[0];
  let rest = arrA.slice(1)

  if (arrA.length === 1) return [firstEl.concat(el)]; // base

  return [firstEl.concat(el)].concat(addEl(rest, el)) 
}

整合后的单递归实现 #

当然可以把两个递归逻辑合并到一个函数里。核心思路是在递归生成前n-1个元素的子集后，直接在同一个函数里完成「给每个子集添加当前元素」的递归操作，不需要额外的addEl函数。

修改后的代码如下：

let arr = []
console.log(JSON.stringify(subsets(arr))); // [[]]
arr = [1]
console.log(JSON.stringify(subsets(arr))); // [[], [1]]
arr = [1,2]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(JSON.stringify(subsets(arr))); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

function subsets(arr) {
  // 基准情况：空数组返回包含空数组的数组
  if (arr.length === 0) return [[]];

  const lastEl = arr[arr.length - 1];
  // 递归获取前n-1个元素的所有子集
  const prevSubsets = subsets(arr.slice(0, -1));

  // 内部递归函数：给子集数组中的每个元素添加当前元素
  function addElementToSubsets(subsetArr) {
    if (subsetArr.length === 0) return [];
    // 给第一个子集添加元素，再递归处理剩余子集
    return [subsetArr[0].concat(lastEl)].concat(addElementToSubsets(subsetArr.slice(1)));
  }

  // 合并原子集和添加元素后的子集
  return prevSubsets.concat(addElementToSubsets(prevSubsets));
}

逻辑说明 #

1. 保留原基准情况：输入数组为空时，返回[[]]。
2. 递归生成前n-1个元素的子集prevSubsets。
3. 在subsets内部定义递归函数addElementToSubsets，作用和原addEl一致——遍历子集数组，给每个子集添加最后一个元素，通过递归完成遍历。
4. 合并原子集和添加元素后的子集，返回最终结果。

另外你注释里提到的map迭代写法其实更简洁，但如果要坚持纯递归实现，上面的单函数版本就可以满足需求。

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