LeetCode之回溯算法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。因为回溯的本质是穷举，换句话说就是暴力解法，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

回溯搜索的遍历过程通常是一个N叉树的结构：

回溯算法模板框架如下：

回溯方法用backtracking名字表示，方法都是用void返回，然后定义终止条件，最后进行收集结果。掌握这个模版，我们所做的各种回溯算法题都离不开这个模版。

void backtracking(参数) {
    if (终止条件) {
        收集结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        添加组合;
        backtracking(路径，选择列表); // 递归，参数修改成下一层级状态
        回溯操作：撤销处理结果，回到上层分支
    }
}

各题题解:

    //解法参考自：https://www.bilibili.com/video/BV1854y1m7WR/?spm_id_from=333.337.search-card.all.click&vd_source=40c24e77b23dc2e50de2b7c87c6fed59

//            ###### [组合总和](https://leetcode.cn/problems/combination-sum/)

    /**
     * dfs的 return条件是 target == 0，找到条件也是 target == 0
     */
    class Solution {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates); //先排序，用于可以剪枝操作
            dfs(candidates, target, 0);
            return result;
        }

        /**
         * 深度优先回溯算法
         * @param candidates 候选集合
         * @param target 剩余需要组合的值
         * @param start 在候选集合中的位置
         */
        public void dfs(int[] candidates, int target, int start) {
            if (target == 0) {
                //找到这个组合，当组合放入结果，然后结束这个层级往下
                result.add(new ArrayList<>(path));
                return;
            }

            //没有找到，则继续从当前候选序列里面取出，候选序列的起始为candidates的idx下标
            for (int i=start;i<candidates.length;i++) {
                //剪枝操作：如果当前canditates[i]大于target了，则这个分支的选取都结束了
                if (candidates[i] > target) {
                    break;
                }

                //先试着把当前数放入组合
                path.add(candidates[i]);
                //继续从i开始选数，因为数可以取重复的;然后转移状态，tagert要为减去candidates[i]的新值；继续dfs往下一层搜索
                dfs(candidates, target-candidates[i], i);
                path.remove(path.size()-1); //回溯：删除最新添加的数，走for循环的下一个i，即走并行的下一个分支
            }
        }
    }

//            ###### [子集](https://leetcode.cn/problems/subsets/)
    /**
     * dfs的 return条件是 找的序号等于了数组长度，找到条件是 只要添加了新元素就是新的结果
     */
    class Solution1 {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> subsets(int[] nums) {
            result.add(new ArrayList<>()); //空集也是子集
            dfs(nums, 0);
            return result;
        }

        public void dfs(int[] nums, int start) {
            if (start >= nums.length) {
                return;
            }

            for (int i=start;i<nums.length;i++) {
                path.add(nums[i]);
                //在子集里，只要path组合新增了，就是一个新的子集，就需要添加到result里面去
                result.add(new ArrayList<>(path));
                dfs(nums, i+1); //往下层走，i需要+1，因为不能元素不能重复
                path.remove(path.size()-1); //回溯回到上层分支
            }
        }
    }

//            ###### [全排列](https://leetcode.cn/problems/permutations/)
    /**
     * dfs的 return条件是 path.size == nums.leng，即所有元素都找完一遍了；找到条件也是 path.size == nums.leng
     */
    class Solution2 {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            dfs(nums);
            return result;
        }

        public void dfs(int[] nums) {
            if (path.size() == nums.length) { //结束条件是 搜索长度满了，该全排列结束
                result.add(new ArrayList<>(path));
                return;
            }

            for (int i=0;i<nums.length;i++) {
                //去重
                if (path.contains(nums[i])) {
                    continue;
                }

                path.add(nums[i]);
                dfs(nums);
                path.remove(path.size()-1);
            }
        }
    }

参考：https://www.bilibili.com/video/BV1854y1m7WR/?spm_id_from=333.337.search-card.all.click&vd_source=40c24e77b23dc2e50de2b7c87c6fed59