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)


相关推荐

  • 输入法个性化怎么设置_手机输入键盘怎么个性化设置

    输入法个性化怎么设置_手机输入键盘怎么个性化设置个性化设置技巧(补充输入法)子墨居士前言本次的内容大部分为推送。本打算自己推荐几款比较好用的桌面整理软件,然而最近事情越来越多,这部分的内容分享已经有很多不错的文章。就允许我偷一次懒呗(…

    2022年10月29日
  • 远程桌面 指定端口_request获取ip地址

    远程桌面 指定端口_request获取ip地址iocp模型的tcp服务端若采用AcceptEx接受连接,在有客户端连接后要获取客户端的ip和端口信息流程:AcceptEx在工作线程收到客户端连接时复制listensocket的信息到新客户端的socketsetsockopt(pOverlapped->hSocket,SOL_SOCKET,SO_UPDATE_ACCEPT_CONTEXT,(cha…

  • Vue:router的beforeEach是什么「建议收藏」

    Vue:router的beforeEach是什么「建议收藏」来自:https://router.vuejs.org/zh/guide/advanced/navigation-guards.html#全局守卫正如其名,vue-router提供的导航守卫主要用来通过跳转或取消的方式守卫导航。有多种机会植入路由导航过程中:全局的,单个路由独享的,或者组件级的。记住参数或查询的改变并不会触发进入/离开的导航守卫。你可以通过观察$route对象来应对这…

  • listview排序功能_listview用法

    listview排序功能_listview用法ListViewSorterlistviewSort=newListViewSorter();this.lsv1.ListViewItemSorter=listviewSort;this.lsv1.Sort();    classListViewSorter:IComparer   {        privateintcolumnToSort;     

  • 计算机发展史的故事_了解计算机的发展史

    计算机发展史的故事_了解计算机的发展史核心提示:男人去嫖娼,就如你下馆子吃饭一样没多大区别,也没有多复杂的动机。男人自己的性欲和食欲一样,是无关感情爱情的。但几乎所有男人都明了:女人如果心甘情愿被人压在下面,这事关女人的感情。男人能把性和爱分开,而女人很难做到。计算工具的演化经历了由简单到复杂、从低级到高级的不同阶段,如从“结绳记事”中的绳结到算筹、算盘计算尺、机械计算机等。它们在不同的历史时期发挥了各自的历史作用,同时也启发了现代电…

    2022年10月19日
  • Elasticsearch数据库

    Elasticsearch数据库1、什么是Elasticsearch1、概念以及特点        1、Elasticsearch和MongoDB/Redis/Memcache一样,是非关系型数据库。是一个接近实时的搜索平台,从索引这个文档到这个文档能够被搜索到只有一个轻微的延迟,企业应用定位:采用RestfulAPI标准的可扩展和高可用的实时数据分析的全文搜索工具。   2、可拓展:支持一主多从且扩容简易,只要clust…

发表回复

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

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