backtracking 经典题选编(1)

回溯法三部曲

递归函数的返回值及其参数（是否定义全局变量来存放结果）
回溯函数终止条件（怎样是到达叶子节点）
单层搜索的过程（注意choose explore unchoose）

LeetCode 77. Combinations

基础版（无剪枝）

回溯法的搜索过程就是一个树型结构的遍历过程。

for循环用来横向遍历，递归的过程是纵向遍历。

List<List<Integer>> res;
LinkedList<Integer> list;
public List<List<Integer>> combine(int n, int k) {
    this.res=new ArrayList<>();
    this.list=new LinkedList<>();
    backtracking(n,k,1);
    return this.res;
}

void backtracking(int n, int k, int start){ //回溯法用来解决k层for循环嵌套的问题
    if(list.size()==k){
        res.add(new LinkedList<>(list));
        return;
    }
    for (int i = start; i <= n; i++) {//每层内开启循环
        list.add(i);
        backtracking(n,k,i+1);
        list.removeLast();
    }
}

加强版（有剪枝）

例如，n = 4，k = 4的话，

第一层for循环的时候，从元素2开始的遍历都没有意义了，因为第一层必须选择1；
在第二层for循环，从元素3开始的遍历都没有意义了，因为第二层必须选择2；

一般而言，

当前 list.size()==size, 加上当前层 1 个元素后，后续递归层还需要 (k-size-1) 个元素
后续递归层的起点为 i+1, 终点为n, 共有 n-i 个元素
因此为满足后续递归层的元素数量要求，n-i >= k-size-1, 即 i <= n-k+size+1, 而不是i<=n

public class LeetCode77 {
    List<List<Integer>> res;
    LinkedList<Integer> list;
    public List<List<Integer>> combine(int n, int k) {
        this.res=new ArrayList<>();
        this.list=new LinkedList<>();
        backtracking(n,k,1);
        return this.res;
    }

    void backtracking(int n, int k, int start){
        if(list.size()==k){
            res.add(new LinkedList<>(list));
            return;
        }
        int size=list.size();
        for (int i = start; i <= n-k+size+1; i++) { //i <= n-k+size+1
            list.add(i);
            backtracking(n,k,i+1);
            list.removeLast();
        }
    }
    
}

LeetCode 46. Permutations

46. Permutations

Given an array nums of distinct integers, return all the possible permutations.

不包含重复元素，无需考虑去重

引入used数组来判断是否该考虑该元素

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    boolean[] used=new boolean[nums.length];
    helper(res,new ArrayList<>(),nums,used);
    return res;
}

void helper(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] used){
    if(list.size()==nums.length){
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if(used[i]){ //该元素以进入list，直接跳过
            continue;
        }
        //choose;explore;unchoose
        list.add(nums[i]); //该元素还没进入list,应该加入进去
        used[i]=true;
        helper(res,list,nums,used);
        list.remove(list.size()-1);
        used[i]=false;
    }
}

LeetCode 47. Permutations II

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

同样的，排列问题引入used数组，来判断是否该考虑该元素

包含重复元素，需要考虑去重

如何去重：

先数组排序

```cpp
// used[i - 1] == true，说明同一树枝nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}


```java
public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    boolean[] visited=new boolean[nums.length];
    Arrays.sort(nums);
    backtracking(res,new ArrayList<>(),nums,visited);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] visited){
    if(list.size()==nums.length){
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if(visited[i]){
            continue;
        }
        if(i>=1 && nums[i]==nums[i-1] && !visited[i-1]){
            continue;
        }
        list.add(nums[i]);
        visited[i]=true;
        backtracking(res,list,nums,visited);
        list.remove(list.size()-1);
        visited[i]=false;
    }
}

LeetCode 39. Combination Sum

39. Combination Sum

基础版（无剪枝）

public class LeetCode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        backtracking(res,new ArrayList<>(),candidates,target,0);
        return res;
    }

    void backtracking(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start){
        if(target<0){
            return;
        }
        if(target==0){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) { //无剪枝
            list.add(candidates[i]);
            backtracking(res,list,candidates,target-candidates[i],i);
            list.remove(list.size()-1);
        }
    }
}

加强版（有剪枝）

在求和问题中，排序之后加剪枝是常见的套路！

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(candidates);
    backtracking(res,new ArrayList<>(),candidates,target,0);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start){
    if(target<0){
        return;
    }
    if(target==0){
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        list.add(candidates[i]);
        if(target-candidates[i]<0){
            list.remove(list.size()-1);
            break;
        }
        backtracking(res,list,candidates,target-candidates[i],i);
        list.remove(list.size()-1);
    }
}

LeetCode 40. Combination Sum II

40. Combination Sum II

去重+剪枝

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(candidates);
    boolean[] visited=new boolean[candidates.length];
    backtracking(res,new ArrayList<>(),candidates,visited,target,0);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int[] candidates, boolean[] visited,int target, int start){
    if(target<0){
        return;
    }
    if(target==0){
        res.add(new ArrayList<>(list));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if(i>=1 && candidates[i]==candidates[i-1] && !visited[i-1]){ //用排序+visited数组来去重
            continue;
        }
        list.add(candidates[i]);
        visited[i]=true;
        if(target-candidates[i]<0){ //剪枝，提前跳出循环
            list.remove(list.size()-1);
            visited[i]=false;
            break;
        }
        backtracking(res,list,candidates,visited,target-candidates[i],i+1);
        list.remove(list.size()-1);
        visited[i]=false;
    }
}

LeetCode 216. Combination Sum III

Combination Sum III

排序后剪枝判断

2个剪枝判断：

元素总和不能超过target，若加上本元素总和超过target，则退出本层循环
元素总个数必须正好为k个，引入limit表示还要用的元素个数，当且仅当limit==0时，满足题意

若满足limit-1<0，则limit==0，本层都不能再加元素，直接退出本层循环

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res=new ArrayList<>();
    backtracking(res,new ArrayList<>(),n,k,1);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int target, int limit, int start){
    if(target==0){
        if(limit==0){
            res.add(new ArrayList<>(list));
        }
        //else limit>0, 直接返回
        return;
    }
    for (int i = start; i <= 9; i++) {
        list.add(i);
        if(target-i<0 || limit-1<0){ //2个剪枝条件，满足1个即退出本层循环
            list.remove(list.size()-1);
            break;
        }
        backtracking(res,list,target-i,limit-1,i+1);
        list.remove(list.size()-1);
    }
}

LeetCode 78. Subsets

78. Subsets

法一：间接法

考虑长度为n的不包含重复元素的数组nums（集合）的子集（包括空集和本身）个数为2^n

2^n=从nums[0]到nums[n-1],每一个元素都有两种情况，取或不取

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> judge=new ArrayList<>(); //引入judge，judge.get(i)==0表示nums[i]不进入该子集，vice versa
    backtracking(res,judge,nums);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> judge, int[] nums){
    if(judge.size()==nums.length){
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < judge.size(); i++) {
            if(judge.get(i)==1){
                list.add(nums[i]);
            }
        }
        res.add(list);
        return;
    }
    judge.add(0);
    backtracking(res,judge,nums);
    judge.remove(judge.size()-1);
    judge.add(1);
    backtracking(res,judge,nums);
    judge.remove(judge.size()-1);
}

法二：直接法

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    backtracking(res,new ArrayList<>(),nums,0);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int[] nums, int start){
    res.add(new ArrayList<>(list));//无需判断，见一个加一个，因为见到的都是子集
    if(start>=nums.length){
        return;
    }
    for (int i = start; i < nums.length; i++) {
        list.add(nums[i]);
        backtracking(res,list,nums,i+1);
        list.remove(list.size()-1);
    }
}

LeetCode 90. Subsets II

90. Subsets II

子集直接法（见一个加一个）+排序去重

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(nums);
    boolean[] visited=new boolean[nums.length];
    backtracking(res,new ArrayList<>(),nums,visited,0);
    return res;
}

void backtracking(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] visited,int start){
    res.add(new ArrayList<>(list));
    if(start>=nums.length){
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if(i>=1 && nums[i]==nums[i-1] && !visited[i-1]){//经典 排序+visited去重
            continue;
        }
        list.add(nums[i]);
        visited[i]=true;
        backtracking(res,list,nums,visited,i+1);
        list.remove(list.size()-1);
        visited[i]=false;
    }
}

IVN

回溯法(1)

backtracking 经典题选编(1)

回溯法三部曲

LeetCode 77. Combinations

基础版（无剪枝）

加强版（有剪枝）

LeetCode 46. Permutations

LeetCode 47. Permutations II

LeetCode 39. Combination Sum

基础版（无剪枝）

加强版（有剪枝）

LeetCode 40. Combination Sum II

LeetCode 216. Combination Sum III

LeetCode 78. Subsets

法一：间接法

法二：直接法

LeetCode 90. Subsets II