1. 基本模板

class Solution {
    public List<List<元素类型>> 方法名(参数列表){
        //返回answer容器集合
        List<List<元素类型>> ans = new ArrayList<>();
        if (返回空集合条件) return ans;
        //返回answer容器集合子集
        List<元素类型> path = new ArrayList<>();
        //标记数组，对使用过的元素进行标记
        boolean[] used = new boolean[数组长度];
        //首先全部标记为未使用false
        Arrays.fill(used);
        backtrack(ans,path,遍历目标,遍历开始位置,used);
        return ans;
    }
    //回溯函数
    public void backtrack(List<List<元素类型>> ans,List<元素类型> path,遍历目标，遍历开始位置，boolean[] used) {
        if (遍历成功条件){
            //向answer容器中添加path结果
            ans.add(new ArrayList<>(path));
            return;
        }
        else {
            for (int i = 开始位置;判断条件;i++) {
                if (!used[i]){
                    path添加操作;
                    //used数组标记已经使用
                    used[i] = true;
                    //沿着这条路径继续遍历
                    backtrack(List<List<元素类型>> ans,List<元素类型> path,遍历目标，遍历开始位置更新，boolean[] used);
                    //回溯时更改used数组使用情况
                    used[i] = false;
                    path移除操作
                }
            }
        }
    }
}

2. 经典例题

2.1 组合

组合

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(n == 0 || k == 0) return res;
        backtrack(res,list,n,k,0,1);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> list,int n,int k,int sum,int start){
        //如果list中的元素数目sum已经达到目标要求k则返回
        if(sum == k){
            res.add(new ArrayList(list));
            return;
        }
        //倘若没有达到则从起始位置start开始往后遍历
        for(int i = start;i <= n;i++){
            list.add(i);
            backtrack(res,list,n,k,sum + 1,i + 1);
            list.remove(list.size() - 1);
        }
    }
}

2.2 组合总和

组合总和

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(candidates == null || candidates.length == 0 || target < 0){
            return res;
        }
        //对数组进行排序，从小到大依次遍历
        Arrays.sort(candidates);
        backtrack(res,path,candidates,target,0);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> path,int[] candidates,int target,int index){
        //如果target等于0则返回
        if(target == 0){
            res.add(new ArrayList<>(path));
        }
        else{
            //继续向后遍历，从下表index处开始
            for(int i = index;i < candidates.length;i++){
                //如果candidates[i]处的值比target还大，证明i之后的值也一定比target大，则这条路径结束并返回
                if(target - candidates[i] < 0){
                    break;
                }
                //如果candidates[i]处的值比target小，则将candidates[i]加入path
                path.add(candidates[i]);
                //继续沿着这条路径遍历，target更新为target - candidates[i]，由于同一个数字可以重复使用，所以index不用更新
                backtrack(res,path,candidates,target - candidates[i],i);
                //回溯返回时需要将path中的最后一个数字移除
                path.remove(path.size() - 1);
            }
        }
    }
}

2.3 组合总和2

组合总和2

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if(candidates.length == 0 || candidates == null || target < 0){
            return res;
        }
        //对数组进行排序，从小到大依次遍历
        Arrays.sort(candidates);
        backtrack(res,path,candidates,target,0);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> path,int[] candidates,int target,int index){
        //如果target等于0则返回
        if(target == 0){
            res.add(new ArrayList<>(path));
        }
        else{
            //继续向后遍历，从下表index处开始
            for(int i = index;i < candidates.length;i++){
                //如果candidates[i]处的值比target还大，证明i之后的值也一定比target大，则这条路径结束并返回
                if(target - candidates[i] < 0){
                    break;
                }
                //如果candidates[i]处的值比target小，则将candidates[i]加入path
                path.add(candidates[i]);
                //继续沿着这条路径遍历，target更新为target - candidates[i]，由于同一个数字不可以重复使用，所以index更新为i+1
                backtrack(res,path,candidates,target - candidates[i],i + 1);
                //如果candidates中有重复元素，则重复元素可以跳过不用再次遍历，
                //即candidates下一个元素和当前路径最后一个元素相同时则跳过candidates的这个元素，进行去重操作
                while(i + 1 < candidates.length && path.get(path.size() - 1) == candidates[i + 1]){
                    i++;
                }
                path.remove(path.size() - 1);
            }
        }
    }
}

2.4 全排列

全排列

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0) return res;
        List<Integer> path = new ArrayList<>();
        //使用used数组记录nums中对应元素的使用情况
        boolean[] used = new boolean[nums.length];
        //首先将所有元素标记为未使用
        Arrays.fill(used,false);
        backtrack(res,path,nums,0,used);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> path,int[] nums,int index,boolean[] used){
        //如果path中的元素数目等于nums数组大小，则将此条路径加入结果res中
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        else{
            //遍历nums数组
            for(int i = 0;i < nums.length;i++){
                //如果当前位置元素没有使用过，则将当前元素加入path，并且将使用情况更新为已经使用
                if(!used[i]){
                    path.add(nums[i]);
                    used[i] = true;
                    //继续遍历nums数组下一个元素
                    backtrack(res,path,nums,index + 1,used);
                    //回溯返回时将used[i]使用情况重新更新为未使用
                    used[i] = false;
                    //删除path路径中最后一个元素
                    path.remove(path.size() - 1);
                }
            }
        }
    }
}

2.5 全排列2

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length == 0) return res;
        Arrays.sort(nums);
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used,false);
        backtrack(res,path,nums,0,used);
        return res;
    }
    public void backtrack(List<List<Integer>> res,List<Integer> path,int[] nums,int index,boolean[] used){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        else{
            for(int i = 0;i < nums.length;i++){
                if(!used[i]){
                    path.add(nums[i]);
                    used[i] = true;
                    backtrack(res,path,nums,index + 1,used);
                    used[i] = false;
                    //唯一与全排列1不同的位置，需要进行去重操作
                    while(i + 1 < nums.length && path.get(path.size() - 1) == nums[i + 1]){
                        i++;
                    }
                    path.remove(path.size() - 1);
                }
            }
        }
    }
}

2.6 单词搜索

单词搜索

class Solution {
    //使用flag标记矩阵中是否存在这个单词
    boolean flag = false;
    public boolean exist(char[][] board, String word) {
        if(board.length == 0 || board[0].length == 0 || word.length() == 0) return false;
        //使用used数组标记矩阵中每个元素的使用情况
        boolean[][] used = new boolean[board.length][board[0].length];
        //遍历矩阵中每个元素，判断该元素是否等于word中的第一个元素
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                if(board[i][j] != word.charAt(0)) continue;
                //如果board[i][j]处的元素等于word的第一个元素，则开始进行回溯
                backtrack(board,word,i,j,0,used);
                //如果此时flag已经等于true，则结束回溯
                if(flag == true) break;
            }
            if(flag == true) break;
        }
        return flag;
    }
    public void backtrack(char[][] board,String word,int i,int j,int index,boolean[][] used){
        //如果此时flag已经等于true，则结束回溯
        if(flag) return;
        //如果board[i][j]处的元素等于word的index下标处的元素，则将board[i][j]处的元素标记为true使用过
        if(board[i][j] == word.charAt(index)){
            used[i][j] = true;
            //如果index长度已经等于word的长度，则证明已经找到这么一条路径
            if(index + 1 == word.length()){
                flag = true;
                return;
            }
            //如果index长度还未到word长度，则还需要进行遍历
            else{
                //向左边进行遍历
                if(i - 1 >= 0){
                    //如果board[i - 1][j]的元素还未使用
                    if(!used[i - 1][j]){
                        used[i - 1][j] = true;
                        backtrack(board,word,i - 1,j,index + 1,used);
                        used[i - 1][j] = false;
                    }
                }
                //向上边进行遍历
                if(j - 1 >= 0){
                    //如果board[i][j - 1]的元素还未使用
                    if(!used[i][j - 1]){
                        used[i][j - 1] = true;
                        backtrack(board,word,i,j - 1,index + 1,used);
                        used[i][j - 1] = false;
                    }
                }
                //向右边进行遍历
                if(i + 1 < board.length){
                    //如果board[i + 1][j]的元素还未使用
                    if(!used[i + 1][j]){
                        used[i + 1][j] = true;
                        backtrack(board,word,i + 1,j,index + 1,used);
                        used[i + 1][j] = false;
                    }
                }
                //向下边进行遍历
                if(j + 1 < board[0].length){
                    //如果board[i][j + 1]的元素还未使用
                    if(!used[i][j + 1]){
                        used[i][j + 1] = true;
                        backtrack(board,word,i,j + 1,index + 1,used);
                        used[i][j + 1] = false;
                    }
                }
                //如果四个方向的元素都被使用，则证明当前元素不可行，返回上一层并将此元素标记为未使用
                used[i][j] = false;
            }
        }
        //如果当前元素不等于word的index下标处的元素，则board[i][j]处的元素不可行，返回上一层并将此元素标记为未使用
        else{
            used[i][j] = false;
            return;
        }
    }
}