77-组合（Combinations）

男娘i 2022-01-22 23:53 319阅读 0赞

题目描述
中文

  1. 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

英文

  1. Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

示例

  1. 输入: n = 4, k = 2
  2. 输出:
  3. [
  4.   [2,4],
  5.   [3,4],
  6.   [2,3],
  7.   [1,2],
  8.   [1,3],
  9.   [1,4],
  10. ]

题目分析

  • 初步分析，返回的是1-n中个数为2的排列组合，组合不能为重复的数字。

    if(cur.size() == k){ //如果长度满足k，就把这种结果添加进去

    1.         res.add(new LinkedList<>(cur));
    2.     }

    for(int i = first;i < n+1; ++i){ //求排列

    1.         cur.add(i);
    2.         put(i+1, k, n, cur);
    3.         cur.removeLast();    //回溯
    4.     }

  • 把这一部分封装起来，形成一个方法。

    public static void put(int first, int k, int n, LinkedList cur){

    1.     if(cur.size() == k){
    2.         res.add(new LinkedList<>(cur));
    3.     }
    4.     for(int i = first;i < n+1; ++i){
    5.         cur.add(i);
    6.         put(i+1, k, n, cur);
    7.         cur.removeLast();    //回溯
    8.     }
    9. }

  • res设置成全局变量，这道题就解决了。

    static List> res = new LinkedList();
    public static List> combine(int n, int k) {

    1.    put(1, k, n, new LinkedList<Integer>());
    2.    return res;
    3. }

  • 这道题的重点在回溯 + 剪枝。

发表评论

表情：
评论列表 （有 0 条评论，319人围观）

还没有评论，来说两句吧...

相关阅读

    相关 77. 组合

    > 保持忙碌。——《人性的优点》 77. 组合 给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。

    悠悠悠悠/ 0 赞/ 164 阅读

    相关 77.组合

    第77题. 组合 题干描述 解题思路 回溯法三部曲 1. 递归函数的返回值以及参数 2. 回溯函数终止条件 3.

    心已赠人心已赠人/ 0 赞/ 1 阅读

    相关 77.组合

    下面我通过讲解一道回溯、递归类型的题目帮助大家快速的理解递归的用法 题目描述： > 给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。你

    素颜马尾好姑娘i素颜马尾好姑娘i/ 0 赞/ 1 阅读

    相关 77. 组合

    给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [

    怼烎@怼烎@/ 0 赞/ 1 阅读