leetcode77-组合

原题

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

示例:

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

解法

思想

leetcode非常多这种类似的题目,例如leetcode39-组合总和leetcode40-组合总和II。多做一些题目心里就有模板了,这道题可以剪枝(根据要求的数量,很多情况搜的是不必要的),但我没剪。

代码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int k;
    int n;
    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        this.n = n;
        List<Integer> list = new ArrayList<>();
        dfs(list,1);        
        return ans;
    }

    public void dfs(List<Integer> list,int min){
        for(int i = min ; i <= n; i++){
            List<Integer> copy = new ArrayList<>(list);
            copy.add(i);
            if(copy.size() == k) {
                ans.add(copy);
                continue;
            }
            dfs(copy,i+1);
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode77-%e7%bb%84%e5%90%88/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月11日 08:43
下一篇 2020年5月12日

相关推荐

  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02420
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0120
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    090
  • leetcode498-对角线遍历

    这是一个Z字形编排问题,JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下…

    2019年11月14日
    0110
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0390
  • leetcode383-赎金信

    原题 https://leetcode.cn/problems/ransom-note/ 解法 记录下字母出现次数 func canConstruct(ransomNote str…

    算法 3天前
    030
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 …

    算法 2020年5月8日
    0110
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04570

发表回复

登录后才能评论