如何不预先生成笛卡尔积，遍历密码锁组合至满足条件后终止

你的原代码逻辑完全偏离需求——你现在是把每个锁轮的所有元素拼成一个字符串来检查，而不是生成每轮选一个元素的密码组合（比如HUGE BLUE BIRD这种），这才会输出错误的结果。

要实现逐个遍历组合且不预先生成全量笛卡尔积（避免内存爆炸），用**深度优先遍历（DFS）**是最优方案：逐个轮次挑选元素，逐步构建组合，每一步都统计当前组合的"A"总数，一旦满足>=3就立即终止所有遍历，返回当前组合。

正确代码实现 #

const array_2d = [
  ["HUGE","TALL","TINY"],
  ["BLUE","CYAN","DARK","GOLD","GRAY"],
  ["BIRD","FISH","GOAT","MOTH"]
];

// 统计单个字符串中"A"的数量
function countA(str) {
  return (str.match(/A/g) || []).length;
}

// 深度优先遍历寻找目标组合
function findTargetCombination(lockWheels) {
  let result = null;

  // 递归遍历函数：当前轮次索引、已选元素数组、累计A数量
  function dfs(wheelIndex, currentCombination, totalA) {
    // 已找到结果，直接终止递归
    if (result !== null) return;

    // 遍历完所有轮次，检查是否达标
    if (wheelIndex === lockWheels.length) {
      if (totalA >= 3) {
        result = currentCombination.join(' ');
      }
      return;
    }

    // 遍历当前轮的每个元素
    for (const item of lockWheels[wheelIndex]) {
      const itemACount = countA(item);
      const newTotalA = totalA + itemACount;

      // 剪枝：当前累计A已达标，直接生成组合并终止
      if (newTotalA >= 3) {
        result = [...currentCombination, item].join(' ');
        return;
      }

      // 递归进入下一轮
      dfs(wheelIndex + 1, [...currentCombination, item], newTotalA);

      // 找到结果就终止当前循环
      if (result !== null) return;
    }
  }

  dfs(0, [], 0);
  return result;
}

// 执行并输出结果
const targetCombination = findTargetCombination(array_2d);
console.log(targetCombination); // 输出: TALL GRAY GOAT

代码关键说明 #

• 避免预生成笛卡尔积：递归过程中只生成当前遍历路径的组合，不会一次性生成所有可能，内存占用极低。
• 剪枝优化：如果当前元素加入后累计"A"数量已达标，直接终止所有遍历，无需继续后续操作。
• 即时终止：一旦找到符合条件的组合，所有递归和循环都会立即停止，保证性能最优。

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