回溯

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

如LeetCode第46题，全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static List<List<Integer>> res;
public List<List<Integer>> permute(int[] nums) {
    res = new ArrayList<>();
    dfs(nums,new ArrayList<>(),new boolean[nums.length]);
    return res;
}
public static void dfs(int[] nums,List<Integer> tmp,boolean[] visd){
    if(tmp.size()== nums.length) {
        res.add(new ArrayList<>(tmp));
        return;
    }
    for (int i = 0; i <nums.length ; i++) {
        if(visd[i]) continue;
        visd[i] = true;     // 标记 去重
        tmp.add(nums[i]);
        dfs(nums,tmp,visd);
        visd[i] = false;    // 解除标记，恢复现场
        tmp.remove(tmp.size()-1);
    }
}