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