栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

77. 组合

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

77. 组合

组合

给定两个整数 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 {
    List> res = new ArrayList<>();
    LinkedList path = new LinkedList<>();
    public List> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
    public void backtracking(int n, int k, int start) {
        //终止条件,当path的长度等于k时,将这个组合添加到res中
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            backtracking(n, k, i + 1);
            //回溯
            path.removeLast();
        }
    }
}

剪枝:如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了。
已经选择的元素个数:path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历。

class Solution {
    List> res = new ArrayList<>();
    LinkedList path = new LinkedList<>();
    public List> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
    public void backtracking(int n, int k, int start) {
        //终止条件,当path的长度等于k时,将这个组合添加到res中
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtracking(n, k, i + 1);
            //回溯
            path.removeLast();
        }
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/949163.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号