如何用非ES6的JavaScript递归生成水果集合的所有合法序列？

嘿，这个代码挑战挺有意思的！你已经意识到嵌套循环的局限性，想转递归是完全正确的思路——递归天生就适合处理这种可变长度的排列组合问题。先聊聊你现有代码的问题，再给你一个能适配任意N的ES5兼容实现方案。

你现有递归代码的核心问题 #

你的思路方向是对的，但几个细节没处理好，导致结果不符合预期：

• 数组引用共享：你直接操作原数组array和fruitRemaining，没有创建副本，递归的所有分支都会共享同一个数组，最终存入fruitSequences的都是最后修改后的数组状态，而不是每个分支的独立序列。
• 回溯逻辑缺失：选完一个水果递归后，没有把它从当前序列中移除（回溯），导致序列只能一直累加，无法回退去尝试其他选择。
• 可用水果处理错误：fruitRemaining.pop()的时机和逻辑不对，应该在每次选择后生成新的可用列表，而不是直接修改原列表。

正确的递归实现（ES5兼容，无外部库） #

我们的目标是生成所有非空的排列（元素不重复，顺序不同算不同序列），核心思路是用回溯法：每次选一个水果加入当前序列，递归处理剩下的水果，递归返回后再把这个水果从当前序列移除，继续尝试下一个选择。

完整代码实现 #

// 定义输入对应的水果集合（严格ES5语法）
var fruitMaps = {
  1: ['Cherry', 'Lime', 'Banana'],
  2: ['Cherry', 'Lime', 'Banana', 'Orange', 'Apple'],
  3: ['Cherry'],
  4: ['Cherry', 'Lime'],
  5: ['Cherry', 'Lime', 'Banana', 'Orange']
};

// 获取并验证用户输入
function getUserInput() {
  var input;
  do {
    input = prompt('请输入1到5之间的数字：');
    // 转成整数并验证合法性
    input = parseInt(input, 10);
  } while (isNaN(input) || input < 1 || input > 5);
  return input;
}

// 核心递归生成函数
function generateAllSequences(fruits) {
  var sequences = [];
  
  // 回溯辅助函数：current=当前构建的序列，available=还能选择的水果列表
  function backtrack(current, available) {
    // 只要当前序列非空，就存入结果（必须存副本，避免引用共享问题）
    if (current.length > 0) {
      sequences.push(current.slice());
    }
    
    // 遍历所有可用水果
    for (var i = 0; i < available.length; i++) {
      // 选择第i个水果
      var selected = available[i];
      current.push(selected);
      // 生成新的可用列表：移除已选的水果（创建副本，不修改原列表）
      var newAvailable = available.slice(0, i).concat(available.slice(i + 1));
      // 递归处理剩下的水果
      backtrack(current, newAvailable);
      // 回溯：把刚才选的水果从当前序列移除，准备尝试下一个选择
      current.pop();
    }
  }
  
  // 初始调用：当前序列为空，可用水果是全部输入的水果
  backtrack([], fruits);
  return sequences;
}

// 运行流程
var selectedNum = getUserInput();
var targetFruits = fruitMaps[selectedNum];
var allSequences = generateAllSequences(targetFruits);

// 按照示例格式输出结果
console.log('生成的所有水果序列：');
allSequences.forEach(function(seq) {
  console.log('[' + seq.join('][') + ']');
});

关键细节解释 #

1. 数组副本的使用：
   • 存入结果时用current.slice()，创建当前序列的副本，避免后续修改影响已保存的结果。
   • 生成newAvailable时用slice和concat创建新数组，不修改原可用列表，保证每个递归分支的可用列表独立。
2. 回溯逻辑：
   每次递归返回后执行current.pop()，把刚才选择的水果从当前序列移除，这样就能回到上一步，尝试选择下一个水果，生成不同的序列。
3. 非空序列保证：
   在backtrack函数开头判断current.length > 0，确保只有非空序列被存入结果，符合题目要求。

测试示例（输入4） #

输入4时，生成的序列和示例完全一致：

[Cherry]
[Cherry][Lime]
[Lime]
[Lime][Cherry]

这个实现可以适配任意数量的输入水果（哪怕以后加入第6个输入类型），完全不需要修改核心递归逻辑。

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