回溯算法part01 算法

回溯算法part01

今日内容：

● 理论基础
● 77. 组合

1.LeetCode77. 组合

https://leetcode.cn/problems/combinations/

模板

		
        //回溯算法模板
        void backtracking(参数) {
				    if (终止条件) {
					       存放结果;
				         return;
				    }

				    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
				        处理节点;
					      backtracking(路径，选择列表); // 递归
				        回溯，撤销处理结果
				    }
				}

未剪枝版本:

//未剪枝版本
class Solution {
    //定义全局变量
    //一维集合
    List<Integer> path=new ArrayList<>();
    //二维集合
    List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        //整个回溯过程抽象为一棵树形结构
        backtracking(n,k,1);
        return result;
        //给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合
        //返回1-4范围内可能的2个数的组合
        //组合可以不按顺序

    }
    //确定回溯的返回值和参数
    //一般回溯算法的返回值是void
    public void backtracking(int n,int k,int beginIndex){
        //beginIndex用来记录每次需要遍历的位置
        //确定终止条件
        //遇到一维数组的大小等于k了，证明我们已经遍历到叶子节点了
        if(path.size()==k){
            //将一维集合放进我们存储结果的二维数组中
            result.add(new ArrayList<>(path));
            return;
        }
        //单层递归//i从1开始
        for(int i=beginIndex;i<=n;i++){
            //将当前取到的值存进一维集合中
            path.add(i);
            //递归，剩余元素，也就是从i+1的位置开始
            backtracking(n,k,i+1);
            //这个函数执行之后，也会将一维集合存进二维集合
            //那么此时我们要清空我们的一维集合，回溯到原来的位置
            path.removeLast();
        }
    }
}

剪枝优化版本:

//剪枝优化
class Solution {
    //定义全局变量
    //一维集合
    List<Integer> path=new ArrayList<>();
    //二维集合
    List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        //整个回溯过程抽象为一棵树形结构
        backtracking(n,k,1);
        return result;
    }
    //确定回溯的返回值和参数
    //一般回溯算法的返回值是void
    public void backtracking(int n,int k,int beginIndex){
        //beginIndex用来记录每次需要遍历的位置
        //确定终止条件
        //遇到一维数组的大小等于k了，证明我们已经遍历到叶子节点了
        if(path.size()==k){
            //将一维集合放进我们存储结果的二维数组中
            result.add(new ArrayList<>(path));
            return;
        }
        //单层递归//i从1开始
        //path.size()为当前一维集合收集到的元素个数
        //k-path.size()为当前一维集合还需要收集多少个元素
        //n-(k-path.size())//总共多少个数-需要收集的元素个数
        //如果是n=4,k=2.当前收集了一个元素，那么还差一个元素未被收集
        //4-1=3//3+1=4
        for(int i=beginIndex;i<=n-(k-path.size())+1;i++){
            //将当前取到的值存进一维集合中
            path.add(i);
            //递归，剩余元素，也就是从i+1的位置开始
            backtracking(n,k,i+1);
            //这个函数执行之后，也会将一维集合存进二维集合
            //那么此时我们要清空我们的一维集合，回溯到原来的位置
            path.removeLast();
        }
    }
}