回溯模板_回溯邮件模版

看了labuladong的回溯推文，来写写自己的理解，同时记录一下模板。

对于一个回溯问题最重要的便是三个点，即已选择的路径、可选择的选择列表、终止条件。

先给出模板吧

def backtrack(路径, 选择列表):
    if 满足结束条件:        
        result.add(路径)       
        return    
    for 选择 in 选择列表:        
        做选择        
        backtrack(路径, 选择列表)        
        撤销选择
1
2
3
4
5
6
7
8

以全排列为例：

若当前节点的位置处于第二排第三个，那么已选择的路径便是3，可选择的选择列表为1、2，终止条件是已选择的路径列表长度为n

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现void backtrack(int[] nums, LinkedList<Integer> track) {   
 // 触发结束条件  
   if (track.size() == nums.length)
   {       
           res.add(new LinkedList(track));      
           return;  
    }    
    for (int i = 0; i < nums.length; i++) 
    {        // 排除不合法的选择        
            if (track.contains(nums[i]))          
                 continue;      
             // 做选择        
             track.add(nums[i]);        
             // 进入下一层决策树        
             backtrack(nums, track);        
             // 取消选择        
             track.removeLast();    
      }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

之前特别不屑记忆模板，现在做题次次被虐！哎呀妈记模板是真香！
所以现在开始记录一下遇到的能够提炼模板的问题！加油！