深度Back结构详解

“深度Back结构”通常指在算法设计中广泛应用的回溯（Backtracking）或基于递归的深度优先搜索（DFS）策略。这类结构通过“尝试—失败—回退—再尝试”的机制，系统地探索所有可能的解空间。

什么是深度Back结构？

深度Back结构是一种通过递归实现的算法范式，其核心思想是：

• 从初始状态出发，逐步构建候选解；
• 若当前路径无法达成目标，则“回退”（backtrack）至上一步；
• 尝试其他分支，直到找到有效解或穷尽所有可能。

典型应用场景

深度Back结构广泛应用于以下问题：

• N皇后问题
• 全排列与组合生成
• 数独求解
• 图的路径搜索（如迷宫问题）

简单代码示例（JavaScript）

以下是一个生成数组全排列的回溯算法实现：

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

  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]); // 找到一个完整解
      return;
    }
    for (let num of nums) {
      if (path.includes(num)) continue; // 剪枝：避免重复
      path.push(num);        // 做选择
      backtrack();           // 递归深入
      path.pop();            // 撤销选择（Back！）
    }
  }

  backtrack();
  return result;
}

为什么叫“Back”？

关键在于 path.pop() 这一行——它在递归返回后“撤销”之前的选择，使程序能尝试其他可能性。这种“前进—回退”的行为，正是“Back”结构的精髓所在。