77-组合（Combinations）

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

**题目描述**  
**中文**

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

**英文**

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

**示例**

输入: n = 4, k = 2
    输出:
    [
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]

**题目分析**

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

if(cur.size() == k){				//如果长度满足k，就把这种结果添加进去
    			res.add(new LinkedList<>(cur));
    		}
    for(int i = first;i < n+1; ++i){			//求排列
    			cur.add(i);
    			put(i+1, k, n, cur);
    			cur.removeLast();	//回溯
    		}

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

public static void put(int first, int k, int n, LinkedList<Integer> cur){
    		if(cur.size() == k){
    			res.add(new LinkedList<>(cur));
    		}
    		for(int i = first;i < n+1; ++i){
    			cur.add(i);
    			put(i+1, k, n, cur);
    			cur.removeLast();	//回溯
    		}
    	}

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

static List<List<Integer>> res = new LinkedList();
    public static List<List<Integer>> combine(int n, int k) {
           put(1, k, n, new LinkedList<Integer>());
           return res;
    	}

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

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

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

相关阅读

相关 LeetCode - Medium - 77. Combinations

Topic Backtracking Description [https://leetcode.com/problems/combinations/][h

浅浅的花香味﹌/ 2023年01月04日 14:53/ 0 赞/ 160 阅读

相关【leetcode.77】组合

一、题目描述给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。示例: > 输入: n = 4, k = 2 > 输出: > \

梦里梦外;/ 2022年12月09日 15:56/ 0 赞/ 219 阅读

相关【LeetCode 77】组合

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

港控/mmm°/ 2022年12月04日 15:58/ 0 赞/ 173 阅读

相关 LeetCode77——Combinations

LeetCode77——Combinations 题意：两个数字n和k，找出所有这样的组合： 1.组合中有k个数字 2.组合是递增 3.组合中的数字是\{1,2

不念不忘少年蓝@/ 2022年08月10日 09:20/ 0 赞/ 140 阅读

相关 leetcode 77. Combinations

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

﹏ヽ暗。殇╰゛Y/ 2022年07月28日 01:06/ 0 赞/ 155 阅读

相关 LeetCode77. 组合

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

迷南。/ 2022年05月12日 06:20/ 0 赞/ 195 阅读

相关 LeetCode 77.Combinations (组合)

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

落日映苍穹つ/ 2022年05月10日 09:06/ 0 赞/ 169 阅读

相关 leetcode:77. 组合

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

你的名字/ 2022年03月18日 01:49/ 0 赞/ 194 阅读

相关 77-组合（Combinations）

题目描述中文给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。英文 Given two integers n and

男娘i/ 2022年01月22日 23:53/ 0 赞/ 206 阅读

相关 77. Combinations

class Solution { public List<List<Integer>> combine(int n, int k) {

灰太狼/ 2021年12月22日 06:51/ 0 赞/ 206 阅读