leetcode #77 in cpp[通俗易懂]

leetcode #77 in cpp[通俗易懂]Giventwointegers n and k,returnallpossiblecombinationsof k numbersoutof1… n.Forexample,If n =4and k =2,asolutionis:[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

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, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution:

It is like permutation(#46 and #47). Thus we still use recurrence to search for combinations. 

given a list called member that contains i numbers in current combination:

if i == k, push member into our final result

else

for each num[j] in member,  i <= j < n;

1. push num[j] into member. 

2. recursively find combination of (num[j+1…..n], k-(i+1) ) 

For example, given [1,2,3,4] and k = 2, 

we start from 1, member is []

push 1 into member. Now member is [1], and we just collect 1 number. We need to collect 1 more.  Go to next recurrence. 

Our current position is 0, we should loop from position 1 to n-1:

1. position 1 which is 2. put 2 into member and member becomes [1,2]. Now we have 2 numbers. put member into final result.

2. position 2 which is 3. put 3 into member and member becomes [1,3]. Now we have 2 numbers, put member into final result

3. position 3 is 4. put 4 into member and member becomes [1,4]. Put member into final result. 

recurrence starting from 1 ends

we start from 2, member is []

push 2 into member. Now member is [2], and we just collect 1 number. We need to collect 1 more.  Go to next recurrence. 

Our current position is 1, we should loop from position 2 to n-1:

1. position 2 which is 3. put 3 into member and member becomes [2,3]. Now we have 2 numbers. put member into final result.

2. position 3 which is 4. put 4 into member and member becomes [2,4]. Now we have 2 numbers, put member into final result

recurrence starting from 2 ends

we start from 3, member is []

push 3 into member. Now member [3], and we just collect 1 number. We need to collect 1 more. Go to next recurrence

Our current position is 2, we should loop from position 3 to n-1:

1. position 3 which is 4. put 4 into member and member becomes [3,4]. Now we have 2 numbers. put member into final result.

recurrence starting from 3 ends

we start from 4, member is []

push 4 into member. Now member [4], and we just collect 1 number. We need to collect 1 more. Go to next recurrence

Our current position is 3, we should loop from position 4 to n-1, but 4 > 3. Thus we terminate the recurrence from 4. member is not pushed. 

Code:

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        
        for(int i = 1; i <=n ; i ++){
            find_combine(i,n, k-1,vector<int>(), res);
        }
        return res;
    }
    void find_combine(int i, int n, int left, vector<int> member, vector<vector<int>> &res){
        member.push_back(i);
        if(left == 0){
            res.push_back(member);
            return;
        }
        else{
            i++;
            while(i<=n){
                find_combine(i, n, left - 1, member, res);
                i++;
            }
        }
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188316.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 少儿编程的学习[通俗易懂]

    少儿编程第一课1.软件的认识2.顶部工具栏的认识3.认识背景,角色,舞台区,以及他们的分别上传4.代码库和代码编辑区第一课1.软件的认识Scratch是由MIT(美国麻省理工学院)针对5至16岁的儿童和青少年设计的可视化程序设计语言与开发环境,专注于用编程实现简单的动画效果。相比其他传统的编程语言,例如VB,Java,Pascal等相比,Scratch语言创建的目的不是为了培养少年程序员…

  • 视音频数据处理入门:UDP-RTP协议解析「建议收藏」

    视音频数据处理入门:UDP-RTP协议解析「建议收藏」本文介绍网络协议数据的处理程序。网络协议数据在视频播放器中的位置如下所示。本文中的程序是一个UDP/RTP协议流媒体数据解析器。该程序可以分析UDP协议中的RTP包头中的内容,以及RTP负载中MPEG-TS封装格式的信息。通过修改该程序可以实现不同的UDP/RTP协议数据处理功能。原理MPEG-TS封装格式数据打包为RTP/UDP协议然后发送出去的流程如下图所示。图中首先每7个MPEG-TSP

  • idea激活码2021(破解版激活)

    idea激活码2021(破解版激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • plc程序设计实例_plc简单应用实例100例

    plc程序设计实例_plc简单应用实例100例一、三相异步电动机的降压启动控制1、三相异步电动机的Y-△降压启动控制将三相异步电动机的Y-△降压启动的继电接触器控制改造为PLC控制系统.(1)确定I/O信号、画PLC的外部接线图(a)主电路(b)PLC的I/O接线图电动机的Y-△降压启动的接线图(2)设计三相异步电动机的Y-△降压启动梯形图电动机的Y-△降压启动控制的梯形图2.三相异步电动机的串自耦变压器降压启动控制将串自耦变压器降压启动的继电接触器控制改造为PLC控制系统:(1)确定I/O信号

  • 向量范数和矩阵范数[通俗易懂]

    向量范数和矩阵范数[通俗易懂]本文分别介绍了向量范数和矩阵范数的定义,以及几种常见的向量范数和矩阵范数

  • windows通过ssh登陆linux服务器(linux 终端快捷键)

    windows通过ssh登陆linux服务器(linux 终端快捷键)window通过ssh连接linux1.window上要安装ssh   下载连接:https://www.mls-software.com/opensshd.html   版本:OpenSSH7.9p1-1   下载好后安装2.linux上启动ssh服务   有些可能没有ssh服务,需要下载安装   2.1检查是否有ssh服务:   判断是否安装ssh服务,可以通过如…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号