-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path051-combinations.py
More file actions
39 lines (28 loc) · 949 Bytes
/
051-combinations.py
File metadata and controls
39 lines (28 loc) · 949 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
36
37
38
39
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(nums: List[int], paths: List[int]):
if len(paths) == k:
res.append(paths)
return
for i, n in enumerate(nums):
backtrack(nums[i+1:], paths+[n])
res = []
if not n or not k:
return res
backtrack(list(range(1, n+1)), [])
return res
def combineV2(self, n: int, k: int) -> List[List[int]]:
def dfs(nums, index, k, paths):
if k == 0:
res.append(paths)
return
for i in range(index, len(nums)):
dfs(nums, i+1, k-1, paths+[nums[i]])
res = []
if not n or not k:
return res
dfs(list(range(1, n+1)), 0, k, [])
return res
print(Solution().combine(4, 2))
print(Solution().combineV2(4, 2))