概念

• 回溯算法，一种通过探索所有可能的候选解来找出所有的解的算法。
• 它采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
• 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
  1. 找到一个可能存在的正确的答案
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案
• 举个类似的生活例子，比如放羊娃的羊在分岔路口走丟了，他顺着不同的岔路口寻找羊，一个岔路口一个岔路口的去尝试找羊。如果找不到羊，继续返回来找到岔路口的另一条路，直到找到羊为止
• 回溯算法其实是一种穷举算法，将所有可能发生的情况都列举一遍，选择可行解或最优解。
• 时间复杂度：O(N!)

应用场景

一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2. 无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3. 子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

回溯算法框架套路

• 穷举找规律，总结出回溯决策树
• 套用回溯算法框架代码

1. 穷举找规律，总结出回溯决策树

• 回溯类型问题的问题，基础也是穷举。我们一般通过穷举找到规律，然后画出回溯决策树就好啦。比如以上全排列的例子。
• 决策树的节点一般有两个属性，就是已走路径和已经可做的选择。在总结决策回溯树的时候需要关注下。

2. 套用回溯算法框架

• 决策一个回溯问题，实际上就是解决一个决策树的遍历过程。需要考虑这三个问题：

  • 已走路径：已做出选择，走过的路径

  • 可选列表：你当前可以做的选择

  • 结束条件：一般走到决策树的叶子节点，它无法再做别的条件选择

• 回溯算法伪代码框架如下：

  //所有路径集合
  allPath := []
  func backTrace (可选列表，已走路径){
       if(满足结束条件){
          allPath.add(已走路径)
          return
       }
       for(选择：可选列表){
          做选择
          backTrace（当前可选列表，已走路径）
          撤销选择
       }
  }
  

示例

1. 全排列问题

• 给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以 按任意顺序 返回答案。

  输入：nums = [1,2,3]
  输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  ----------------------------
  输入：nums = [0,1]
  输出：[[0,1],[1,0]]
  

• code

  func permute(nums []int) [][]int {
      n := len(nums)
      res := [][]int{}
      visited := make([]bool, n)
      path := []int{}
  
      var backtrack = func(idx int) {
          if idx == n {
              temp := make([]int, n)
              copy(temp, path)
              res = append(res, temp)
              return
          }
          for i := 0; i < n; i++ {
              if visited[i] {
                  continue
              }
              visited[i] = true
              path = append(path, nums[i])
              backtrack(idx + 1)
              visited[i] = false
              path = path[:len(path)-1]
          }
      }
  
      backtrack(0)
      return res
  }
  /*
  定义了一个backtrack函数来进行回溯操作。在backtrack函数中，首先判断当前路径是否已经遍历完了所有的数字，如果是，则将当前路径加入到结果集中；否则，遍历所有的数字，如果当前数字已经被访问过，则跳过；否则，将当前数字加入到路径中，并标记当前数字已经被访问过，然后继续回溯下一个数字。当回溯完成后，需要将当前数字的访问状态标记为未访问，并将当前数字从路径中移除，以便回溯到上一个状态。
  
  最后，在主函数中调用backtrack函数，并将结果集返回即可
  */