给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
第一种思路：
调库。
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""import itertoolsreturn list(itertools.combinations(range(1,n+1),k))第二种思路：
回溯。一般问组合的都是回溯。
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""res = []def generate(k, i, tmp):if k == 0:res.append(tmp[:])returnfor j in range(i , n + 1):tmp.append(j)generate(k - 1, j + 1, tmp)tmp.pop()generate(k, 1, [])return res以下写于2019.6.18
class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""res = []def dfs(t, cnt, tmp):if cnt == 0:res.append(tmp[:])for i in range(t + 1, n + 1):dfs(i, cnt - 1, tmp + [i])dfs(0, k, [])return res
本文链接：https://my.lmcjl.com/post/8277.html
展开阅读全文
4 评论