专栏首页用户画像Leetcode No.77 组合

Leetcode No.77 组合

一、题目描述

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

示例:

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

二、解题思路

重点概括:

如果解决一个问题有多个步骤,每一个步骤有多种方法,题目又要我们找出所有的方法,可以使用回溯算法; 回溯算法是在一棵树上的 深度优先遍历(因为要找所有的解,所以需要遍历); 组合问题,相对于排列问题而言,不计较一个组合内元素的顺序性(即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合),因此很多时候需要按某种顺序展开搜索,这样才能做到不重不漏。

回溯算法首先需要画出递归树,不同的树决定了不同的代码实现。下面给出了两种画树的思路。

方法一:根据搜索起点画出二叉树 既然是树形问题上的 深度优先遍历,因此首先画出树形结构。例如输入:n = 4, k = 2,我们可以发现如下递归结构:

如果组合里有 1 ,那么需要在 [2, 3, 4] 里再找 1 个数; 如果组合里有 2 ,那么需要在 [3, 4] 里再找 1数。注意:这里不能再考虑 1,因为包含 1 的组合,在第 1 种情况中已经包含。 依次类推(后面部分省略),以上描述体现的 递归 结构是:在以 n结尾的候选数组里,选出若干个元素。画出递归结构如下图:

说明:

叶子结点的信息体现在从根结点到叶子结点的路径上,因此需要一个表示路径的变量 path,它是一个列表,特别地,path 是一个栈; 每一个结点递归地在做同样的事情,区别在于搜索起点,因此需要一个变量 start ,表示在区间 [begin, n] 里选出若干个数的组合; 可能有一些分支没有必要执行,我们放在优化中介绍。 友情提示:对于这一类问题,画图帮助分析是非常重要的解题方法。

class Solution {
public:
    vector<int> temp;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return ans;
    }
    void dfs(int cur, int n,int k) {
        // 剪枝:temp 长度加上区间 [cur, n] 的长度小于 k,不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        // cur == n + 1 的时候结束递归
        if (cur == n + 1) {
            return;
        }
        // 考虑选择当前位置
        temp.push_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
};

方法二:按照每一个数选与不选画出二叉树

可以按照每一个数选与不选画出二叉树,二叉树最多 n 层。同样可以剪枝。剪枝的思路请见下图「剪枝条件 ② 的加强」。

画一个表格更容易看出边界条件。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        vector<vector<int>> rs;
        dfs(1,n,k,path,rs);
        return rs;
    }
    void dfs(int begin, int n,int k,vector<int> path,vector<vector<int>> &rs) {
       if(k==0){
           rs.push_back(path);
           return;
       }
       if(begin>n-k+1){
           return;
       }
       dfs(begin+1,n,k,path,rs);
       path.push_back(begin);
       dfs(begin+1,n,k-1,path,rs);
       path.pop_back();
    }
};

三、复杂度分析

时间复杂度:我们已经得到了一个时间复杂度为 O(

) 的组合枚举,由于每次记录答案的复杂度为 O(k),故这里的时间复杂度为 O(

*k)

空间复杂度:O(n + k) = O(n),即递归使用栈空间的空间代价和临时数组temp 的空间代价。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-77-组合

    vector<vector<int>> combine(int n, int k) 

    chenjx85
  • leetcode-77-组合

    组合,没有重复的情况(不放回抽样组合) 使用 itertools.combinations 方法,

    Spaceack
  • LeetCode 77. 组合(回溯)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/combinations 著作权归领扣网络所有。商业...

    Michael阿明
  • Leetcode 77. 组合 (排列组合,回溯)

    glm233
  • ​LeetCode刷题实战77:组合

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 力扣77——组合

    原题url:https://leetcode-cn.com/problems/combinations/

    健程之道
  • Leetcode No.175 组合两个表

    编写一个 SQL 查询,满足条件:无论 person 是否有地址信息,都需要基于上述两表提供 person 的以下信息:

    week
  • 组合问题汇总-LeetCode 46、77、39、40、219、377、1014(回溯法,DP,贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations

    算法工程师之路
  • 画解算法 77-组合

    https://leetcode-cn.com/problems/combinations/

    lucifer210
  • 画解算法 77-组合

    https://leetcode-cn.com/problems/combinations/

    灵魂画师牧码
  • Leetcode No.88 合并两个有序数组

    给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。

    week
  • LeetCode50-80题汇总,速度收藏!

    今天把最近发布的50-80篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相信很多人都没看过,如果对于算法感兴趣的,建议可以每篇认真阅读一...

    程序IT圈
  • 【LeetCode】(No.017)电话号码的字母组合

    刷题模块的初衷是恶补数据结构和算法,不管自己的公众号怎样变化,刷题这个模块一定会保留下去,期待自己能成为offer收割机。LeetCode 第十六题传输门:【L...

    PM小王
  • LeetCode No.17 电话号码的字母组合

    输入:"23" 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答...

    week
  • 9月技术文章汇总

    Leetcode名企之路
  • LeetCode 77,组合挑战,你能想出不用递归的解法吗?

    今天是LeetCode第46篇文章,我们一起来LeetCode中的77题,Combinations(组合)。

    TechFlow-承志
  • LeetCode1-100题汇总,希望对你有点帮助!

    时间很快,公众号发布的LeetCode题目,已经达到100道题了。今天把发布的1-100篇LeetCode文章整理一下,平时文章都放在比较末尾,阅读量都不高,相...

    程序IT圈
  • Leetcode打卡 | No.017 电话号码的字母组合

    欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

    小小詹同学
  • Leetcode No.56 合并区间

    以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一...

    week

扫码关注云+社区

领取腾讯云代金券