leetcode【回溯算法—中等】77.组合

文章目录

• 前言
• 题目
• 题解
• 正文
• NO1：回溯法+剪枝
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为回溯算法专题。

---

题目

题目来源leetcode

leetcode地址：77. 组合，难度：中等。

题目描述(摘自leetcode)：

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

示例 1：
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：
输入：n = 1, k = 1
输出：[[1]]
 
提示：
1 <= n <= 20
1 <= k <= n

本地调试代码：

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        ...
    }

    public static void main(String[] args) {
        List<List<Integer>> itemList = new Solution().combine(4, 2);
        for (List<Integer> items : itemList) {
            System.out.println(items);
        }
    }

}

---

题解

使用暴力法我们也可以取出所有的组合，有一个很大的弊端就是，for循环的层数要与k的数量一致，这就造成若是k很大我们无法实时的构造出一定的循环次数。

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> itemList = new ArrayList<>();
        //k的数量就是层数，n为要遍历的范围区间
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <= n; j++) {
                List<Integer> item = new ArrayList<>();
                item.add(i);
                item.add(j);
                itemList.add(item);
            }
        }
        return itemList;
    }

    public static void main(String[] args) {
        List<List<Integer>> itemList = new Solution().combine(4, 2);
        for (List<Integer> items : itemList) {
            System.out.println(items);
        }
    }

}

---

正文

NO1：回溯法+剪枝

思路：使用一个startIndex变量来进行调节范围，这里采用递归回溯的方法来进行组合。

代码：

//用于记录所有组合的列表
List<List<Integer>> result = new ArrayList<>();
//记录每个组合。(频繁添加、删除使用链表集合)
LinkedList<Integer> path = new LinkedList<>();

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

/**
  * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
  * @param n 组合数的范围
  * @param k 组合数的数量
  * @param startIndex 用于记录本地递归集合中哪个值开始遍历
  */
private void combineHelper(int n, int k, int startIndex){
    //终止条件
    if(path.size() == k){ //这里用于限制组合数
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = startIndex; i <= n ; i++) {
        path.add(i);
        combineHelper(n,k,i+1);
        path.removeLast();//回溯：删除组合中的最后一个元素
    }
}

上面的题解其实会有一些额外无意义的操作，例如n=4，k=4时，若是起始点为startIndex+1，之后的每组递归掉用其实都凑不齐4个，那么这些操作我们其实可以进行避免，也就是进行剪枝操作（避免递归调用）：

这里引用代码回想录题解的图（原图地址在右边文章链接里）：第77题. 组合

将上面的第26行代码修改为：

//k - item.size()：等待组合的剩余数量
//n=4，k=2情况：对于上来第一波循环其范围则为  i<= 4-(2-0)+1，也就是i<=3，因为每组是2个，所以直接会将i=4的情况直接进行剪枝！
for (int i = startIndex; i <= n - (k - item.size()) + 1; i++) {

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—第77题. 组合

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.9