当前位置：首页 > article >正文

LeetCode刷题记录：（11）组合（初识回溯算法）

article 2024/11/5 22:47:25

在这里插入图片描述

leetcode传送通道

暂时记录，这篇没啥营养，不用看了

class Solution {

    List<List<Integer>> result = new ArrayList<>(); // 存所有组合
    List<Integer> path = new LinkedList<>(); //存每一个组合

    public List<List<Integer>> combine(int n, int k) {
        recur(n, k, 1);
        return result;

    }

    // 定义递归/回溯函数
    private void recur(int n, int k, int startNum){
        // 结束条件
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        // 感觉回溯就是通过递归解决直接写写不完的暴力
        // for(int i=startNum; i<=n; i++){
        //     path.add(i);
        //     recur(n,k,i+1);
        //     path.removeLast(); // 关键
        // }

        // 优化：剪枝，调整i的范围，把n替换成i的最大到达位置，该位置之后组合不足k个不用遍历
        for(int i=startNum; i<=n-(k-path.size())+1; i++){
            path.add(i);
            recur(n,k,i+1);
            path.removeLast(); // 关键
        }
    }
}