【leetcode刷题】20T40-组合
https://leetcode-cn.com/problems/combinations/
【题目】
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
【思路】
使用两个数组，一个存储当前组合的前几个元素，一个存储剩余的元素。
遍历剩余元素，依次添加至组合中，更新组合元素及剩余元素，进行递归。当组合元素个数等于k时，将该组合添加至结果中。
这种想法的空间复杂度非常高，有更好的想法吗？
由于是组合问题，元素内部的顺序是没有关系的。
那么，小于组合中元素最大值的元素，不必保留在剩余元素数组中。
比如，组合中最大元素是4，那么剩余元素不必保留1、2、3，而保留的是5, 6, …, n。
为什么呢？
虽然[4,1]可能是一个解，但是在其他遍历中，会遍历到[1, 4]这个解。
【代码】
python版本
解法1
class Solution(object):
def gen(self, now, reserve, k, res):
if k == 0:
res.append(now)
for i, r in enumerate(reserve):
now_tmp = copy.copy(now)
now_tmp.append(r)
reserve_tmp = copy.copy(reserve)
reserve_tmp = reserve_tmp[i+1:]
self.gen(now_tmp, reserve_tmp, k - 1, res)
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
ls = list(range(1, n+1))
if k == n:
return [ls]
if k == 1:
return [[lsi] for lsi in ls]
res = []
for i in range(1, n+1):
tmp = copy.copy(ls)
tmp = tmp[i:]
self.gen([i], tmp, k - 1, res)
return res
解法二
class Solution(object):
def gen(self, n, now, k, res):
if k == 0:
res.append(now)
return
if now[-1] + k > n:
return
for i, r in enumerate(range(now[-1] + 1, n + 1)):
now_tmp = copy.copy(now)
now_tmp.append(r)
self.gen(n, now_tmp, k - 1, res)
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
# 特殊情况
if k == n:
return [list(range(1, n+1))]
if k == 1:
return [[lsi] for lsi in list(range(1, n+1))]
res = []
for i in range(1, n + 1):
self.gen(n, [i], k - 1, res)
return res
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-04-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
