【Leetcode】77. 组合

Pink 发布于2019-07-30 17:56 / 1154人阅读

摘要：题目给定两个整数和，返回中所有可能的个数的组合。示例输入输出题解这道题目我就不做解析了，就是全排列的变种，全排列用的方法，我们之前已经解析过好几期了，都是一套解题模板，直接记住这种题目的模板即可快速掉。版本版本回溯题目第个排列全排列全排列

题目

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

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

题解

这道题目我就不做解析了，就是全排列的变种，全排列用backtrack的方法，我们之前已经解析过好几期了，都是一套解题模板，直接记住这种backtrack题目的模板即可快速A掉。

java版本

class Solution {
    public List> combine(int n, int k) {
        List> res = new ArrayList<>();
        backtrack(res, n, 1, k, new ArrayList<>());
        return res;
    }

    public void backtrack(List> res, int n, int num, int k, List list) {
        if (list.size() == k) {
            res.add(new ArrayList<>(list));
        } else {
            for (int i = num; i <= n; i++) {
                list.add(i);
                backtrack(res, n, i + 1, k, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

python版本

class Solution:
    def backtrack(self, res, n, nums, k, current):
        if len(current) == k:
            res.append(current.copy())
        else:
            for i in range(nums, n + 1):
                current.append(i)
                self.backtrack(res, n, i + 1, k, current)
                current.pop()

    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        self.backtrack(res, n, 1, k, [])
        return res

回溯题目

【Leetcode】60. 第k个排列

【Leetcode】47. 全排列 II

【Leetcode】46.全排列

GPU云服务器云服务器 LeetCode LeetCode_String vps77 cdn77

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42512.html

【Leetcode】77. 组合

摘要：题目给定两个整数和，返回中所有可能的个数的组合。示例输入输出题解这道题目我就不做解析了，就是全排列的变种，全排列用的方法，我们之前已经解析过好几期了，都是一套解题模板，直接记住这种题目的模板即可快速掉。版本版本回溯题目第个排列全排列全排列题目给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。示例: 输入: n = 4, k = 2 输出: [ [2,...

figofuture 2019-08-19 11:13 评论0 收藏0
LeetCode 刷题（九）算法入门--回溯

摘要：用来存放每一个可能的结果最终结果深度优先遍历剪枝当遍历到底个数是，如果的元素个数剩余元素个数时，就不满足条件了中元素个数达到，表示深度优先遍历到达最深处了。 77. 组合77. 组合77. 组合给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任...

morgan 2021-11-15 11:38 评论0 收藏0
leetcode77. Combinations

摘要：再在前一种情况下继续下一轮的遍历，并将结果添加到队列末尾。思路二递归其实，通过递归的方法我们也可以在前一轮的基础上进行下一轮的计算。题目要求 Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2...

garfileo 2019-08-15 10:43 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
LeetCode 子集合，排列组合，回文分离等问题的通用递归算法

摘要：通用算法思路总结初始结果列表。可能要将数集排序，方便处理重复元素的情况。书写递归函数，先要考虑原点状况，一般就是考虑什么情况下要将当前结果添加到结果列表中。每当一个元素添加到当前结果中之后，要再调用递归函数，相当于固定了前缀穷举后面的变化。通用算法思路总结：初始结果列表。可能要将数集排序，方便处理重复元素的情况。调用递归函数。书写递归函数，先要考虑原点状况，一般就是考虑什么...

cfanr 2019-08-14 15:54 评论0 收藏0