forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcombinations.py
More file actions
executable file
·104 lines (79 loc) · 2.73 KB
/
combinations.py
File metadata and controls
executable file
·104 lines (79 loc) · 2.73 KB
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class Solution(object):
def combine(self, N, K):
def helper(first, combination):
if len(combination)==K:
answer.append(combination)
else:
for num in xrange(first, N+1):
helper(num+1, combination+[num])
answer = []
helper(1, [])
return answer
"""
`helper()` helps append `combination` to the `answer` if there are already K element in the `combination`.
The parameter `first` means we are only going to use number fisrt~N.
Because we used the smaller number already, or we will have duplicates.
If there are not enough element in the `combination`, it will run through fisrt~N and append all the element `num` to the `combination`, and set the `first` to num+1.
In other words, if we use 3, we will not use 3 and the number below 3 anymore.
The call stack will be
```
N = 4, K = 2.
helper(1, [])
helper(2, [1])
helper(3, [1, 2])
helper(4, [1, 3])
helper(5, [1, 4])
helper(3, [2])
helper(4, [2, 3])
helper(5, [2, 4])
helper(4, [3])
helper(5, [3, 4])
helper(5, [4])
```
"""
class Solution(object):
def combine(self, N, K):
answer = []
combination = []
first = 1
while True:
if len(combination)==K:
answer.append(combination[:])
if len(combination)==K or first>N:
if not combination: return answer
first = combination.pop()+1 #backtrack
else:
combination.append(first)
first+=1
"""
Iterative solution is not so easy to understand.
I suggest you run a easier example on paper, and you will know how it works. (`N = 4 , K = 2`)
For every iterative, we append the combination to the answer if the length is equal to K already.
Adjust the `first` whenever needed (`len(combination)==K or first>N`), if not, keep on appending.
The time complexity is O(N!/(N!(N-K)!)), combination N choose K.
The space complexity is O(N!/(N!(N-K)!)), combination N choose K.
"""
#DFS
class Solution(object):
def combine(self, N, K):
def dfs(n_min, path):
if len(path)==K:
opt.append(path)
return
else:
for n in xrange(n_min, N+1):
dfs(n+1, path+[n])
opt = []
dfs(1, [])
return opt
class Solution(object):
def combine(self, N, K):
def dfs(comb, start, N, K):
if len(comb)==K: ans.append(comb[:])
for n in xrange(start, N+1):
comb.append(n)
dfs(comb, n+1, N, K)
comb.pop()
ans = []
dfs([], 1, N, K)
return ans