Lintcode152 Combinations solution 题解

【题目描述】

Given two integersnandk, return all possible combinations of numbers out of 1 ...n.

组给出两个整数n和k,返回从1......n中选出的k个数的组合。

【题目链接】

www.lintcode.com/en/problem/combinations/

【题目解析】

先枚举第一个数,然后枚举一个比第一个数大的数作为第二个数,……,最后枚举一个比前k-1个数都大的数作为第k个数,这样就能够枚举所有k个数的组合方案,又能够保证不出现重复的情况。

但是由于k是输入的,所以我们需要采取回溯的形式,即以递归嵌套的方式来动态的进行枚举。

然后就只需要在可以的范围内枚举下一个数,添加到current的末尾,这个数需要比last大,并且比n-k+1要小(确保之后的数还有空间)。

在枚举好后,就只需要在current之后添加该数,然后利用回溯的方法,递归的去枚举下一个数。

特别的,当k==0时,说明已经完成了枚举,只需要将current添加到ans末尾即可。

【参考答案】

www.jiuzhang.com/solutions/combinations/

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,351评论 0 33
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 18,132评论 2 36
  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 14,691评论 0 89
  • 因为年轻而敏感的自尊心,才使他们躲避公众的目光来悄然地取走自己那两个不体面的黑家伙,以免遭受许多无言的耻笑! 他现...
    白甫愈疾阅读 3,173评论 0 0
  • by Pavel Puhov
    知否读书阅读 921评论 0 0