回溯算法 - 《数据结构与算法》

回溯概念

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。 所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数

回溯法的效率

回溯法解决的问题

如何理解回溯法

回溯法模板

组合问题

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

剪枝操作

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(n,k,result,1,new ArrayList<>());
        return result;
    }
    private void backtracking(int n,int k,List<List<Integer>> result,int begain,ArrayList<Integer> list){
        if(list.size() == k){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = begain; i <= n; i++){
            list.add(i);
            backtracking(n,k,result,i+1,list);
            list.remove(list.size()-1);
        }
    }
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
    List<String> res = new LinkedList<>();
    Map<Character,String> map = new HashMap<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return res;
        }
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        backtracking(digits,0,"");
        return res;
    }
    private void backtracking(String digits,int index,String path){
        if(index == digits.length()){
            res.add(path);
            return;
        }
        String s = map.get(digits.charAt(index));
        for(int i = 0; i < s.length(); i++){
            path = path + s.charAt(i);
            backtracking(digits,index + 1,path);
            path = path.substring(0,path.length() - 1);
        }
    }
}

39. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>(); //结果集
        List<Integer> path = new ArrayList<>(); //路径结果集
        backtracking(candidates,target,res,path,0,0);
        return res;
    }
    private void backtracking(int[] candidates, int target,List<List<Integer>> res,List<Integer> path,int sum,int start){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start;i < candidates.length;i++){
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates,target,res,path,sum,i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();    //结果集
        List<Integer> path = new ArrayList<>();         //路径集
        Arrays.sort(candidates);                        //排序
        backtracking(candidates,target,res,path,0);
        return res;
    }
    private void backtracking(int[] candidates,int target,List<List<Integer>> res,List<Integer> path,int start){
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start;i < candidates.length; i++){
            if(candidates[i] > target){           //剪枝，去除没必要的搜索
                return;
            }
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            backtracking(candidates,target - candidates[i],res,path,i+1);  
            path.remove(path.size() - 1);
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。说明：所有数字都是正整数。解集不能包含重复的组合。 输入: k = 3, n = 7 输出: [[1,2,4]]

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>(); //存放结果集
        ArrayList<Integer> list = new ArrayList<>();    //存放符合条件的结果
        backtracking(k,n,result,1,list);
        return result;
    }
    private void backtracking(int k,int n,List<List<Integer>> result, int start,ArrayList<Integer> list){
        //终止条件
        if(list.size() == k || n <= 0){
            if(list.size() == k && n == 0){
                result.add(new ArrayList<>(list));
                return;
            }
        }
        for(int i = start;i <= 9;i++){
            //处理节点
            list.add(i);
            //回溯
            backtracking(k,n-i,result,i+1,list);
            //剪枝
            list.remove(list.size() - 1);
        }
    }
}

分割

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backtracking(s,res,path,0);
        return res;
    }
    private void backtracking(String s,List<List<String>> res,List<String> path,int startIndex){
        if(startIndex == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex;i < s.length(); i++){
            if(isPalindrome(s,startIndex,i)){
                //截取字符串长度
                String str = s.substring(startIndex,i+1);
                path.add(str);
                backtracking(s,res,path,i+1);
                path.remove(path.size() - 1);
        }
    }
}
    //判断是否是回文字符串
    private boolean isPalindrome(String s, int left,int right){
        for(int i = left,j = right;i < j;i++,j--){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

子集

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtracking(nums,res,path,0);
        return res;
    }
    private void backtracking(int[] nums,List<List<Integer>> res, List<Integer> path,int startIndex){
        res.add(new ArrayList<>(path));   //子集收集树形结构中所有节点的结果
        if(startIndex == nums.length){    //递归终止条件
            return;
        }
        for(int i = startIndex;i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums,res,path,i+1);
            path.remove(path.size() - 1);
        }
    }
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i< nums.length + 1; i++){
            backtracking(nums,i,0,res,path);
        }
        return res;
    }
    private void backtracking(int[] nums,int len,int startIndex,List<List<Integer>> res,List<Integer> path){
        if(path.size() == len){                //终止条件
            res.add(new ArrayList<>(path));     
            return;
        }
        for(int i = startIndex; i< nums.length; i++){
            if(i > startIndex && nums[i] == nums[i-1]){       //判断是否重复取了
                continue;
            }
            path.add(nums[i]);
            backtracking(nums,len,i+1,res,path);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            result.add(path);
            return result;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }
    private void subsetsWithDupHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

排列

46. 全排列

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        HashMap<Integer,Boolean> visited = new HashMap<>();
        for(int num : nums){
            visited.put(num,false);
        }
        backtracking(nums,result,visited,new ArrayList<>());
        return result;
    }
    private void backtracking(int[] nums, List<List<Integer>> result,HashMap<Integer,Boolean> visited,ArrayList<Integer> list){
        if(list.size() == nums.length){
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i< nums.length; i++){
            int num = nums[i];
            if(!visited.get(num)){
                list.add(num);
                visited.put(num,true);
                backtracking(nums,result,visited,list);
                list.remove(list.size() - 1);
                visited.put(num,false);
            }
        }
    }
}

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

class Solution {
    public List<List<Integer>> result = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length == 0){    //判空
            return result;
        }
        //首先给数组排序
        Arrays.sort(nums);
        findUnique(nums,new boolean[nums.length],new LinkedList<Integer>());
        return result;
    }
    public void findUnique(int[] nums, boolean[] visited,LinkedList<Integer> trace){
        //结束条件
        if(trace.size() == nums.length){
            result.add(new LinkedList(trace));
            return ;
        }
        //选择列表
        for(int i = 0; i<nums.length; i++){
            //其次，我们已经选择过的不需要再放进去了
            if(visited[i]) continue;
            //接下来，如果当前节点与他的前一个节点一样，并其他的前一个节点已经被遍历过了，那我们也就不需要了。
            if(i>0 && nums[i] == nums[i-1] && visited[i-1]) break;
            //做出选择
            trace.add(nums[i]);
            visited[i] = true;
            findUnique(nums,visited,trace);
            //撤销选择
            trace.removeLast();
            visited[i] = false;
        }
    }
}

class Solution {
    List<List<Integer>> result = new LinkedList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        if(nums.length == 0) return result;
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backtracking(nums, used);
        return result;
    }
    private void backtracking(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
        // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
        // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
        for(int i = 0; i < nums.length; i++){  
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
                continue;
            }
            if(used[i] == false){   //如果同⼀树⽀nums[i]没使⽤过开始处理
                used[i] = true;      //标记同⼀树⽀nums[i]使⽤过，防止同一树支重复使用
                path.add(nums[i]);    
                backtracking(nums, used);
                path.remove(path.size() - 1); //回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;
            }
        }
    }
}

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。示例 1：

输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]] 示例 2：

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

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return res;
    }
    private void backtracking (int[] nums, int start) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }
        int[] used = new int[201];
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                    (used[nums[i] + 100] == 1)) continue;
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, words, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]){
            return false;
        }
        if(k == word.length - 1){
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
            dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}