JavaScript回溯算法详解与实现

function backtrack(path, options, result) {
  // 满足结束条件
  if (满足条件) {
    result.push([...path]); // 注意：拷贝当前路径
    return;
  }

  for (let i = 0; i < options.length; i++) {
    // 做选择
    path.push(options[i]);

    // 进入下一层决策
    backtrack(path, 新的选择列表, result);

    // 撤销选择（回溯）
    path.pop();
  }
}

function permute(nums) {
  const result = [];

  function backtrack(path, used) {
    // 结束条件：路径长度等于原数组长度
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let num of nums) {
      if (used.has(num)) continue;

      // 做选择
      path.push(num);
      used.add(num);

      // 进入下一层
      backtrack(path, used);

      // 撤销选择
      path.pop();
      used.delete(num);
    }
  }

  backtrack([], new Set());
  return result;
}

// 示例
console.log(permute([1, 2, 3]));
// 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

function subsets(nums) {
  const result = [];

  function backtrack(start, path) {
    // 每个节点都是有效解，直接加入
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);           // 做选择
      backtrack(i + 1, path);       // 下一层从i+1开始避免重复
      path.pop();                   // 撤销选择
    }
  }

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

// 示例
console.log(subsets([1, 2, 3]));
// 输出: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]