FilesExpand file tree

master

/

combinations.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (41 loc) · 1.17 KB

master

/

combinations.py

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (41 loc) · 1.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(k * C(n, k))

# Space: O(k)

class Solution(object):

def combine(self, n, k):

"""

:type n: int

:type k: int

:rtype: List[List[int]]

"""

result, combination = [], []

i = 1

while True:

if len(combination) == k:

result.append(combination[:])

if len(combination) == k or \

len(combination)+(n-i+1) < k:

if not combination:

break

i = combination.pop()+1

else:

combination.append(i)

i += 1

return result

class Solution2(object):

def combine(self, n, k):

"""

:type n: int

:type k: int

:rtype: List[List[int]]

"""

def combineDFS(n, start, intermediate, k, result):

if k == 0:

result.append(intermediate[:])

return

for i in xrange(start, n):

intermediate.append(i+1)

combineDFS(n, i+1, intermediate, k-1, result)

intermediate.pop()

result = []

combineDFS(n, 0, [], k, result)

return result