forked from gavinfish/leetcode-share
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path077 Combinations.py
More file actions
35 lines (30 loc) · 807 Bytes
/
077 Combinations.py
File metadata and controls
35 lines (30 loc) · 807 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
'''
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],
]
'''
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
if k == 1:
return [[i + 1] for i in range(n)]
result = []
if n > k:
result = [r + [n] for r in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)
else:
result = [r + [n] for r in self.combine(n - 1, k - 1)]
return result
if __name__ == "__main__":
assert Solution().combine(4, 2) == [[1, 4], [2, 4], [3, 4], [1, 3], [2, 3], [1, 2]]