FilesExpand file tree

master

/

all_combinations.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

46 lines (36 loc) · 1.19 KB

master

/

all_combinations.py

Copy path

Top

File metadata and controls

• Code
• Blame

46 lines (36 loc) · 1.19 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

46

"""

In this problem, we want to determine all possible combinations of k

numbers out of 1 ... n. We use backtracking to solve this problem.

Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!)))

"""

from __future__ import annotations

def generate_all_combinations(n: int, k: int) -> list[list[int]]:

"""

>>> generate_all_combinations(n=4, k=2)

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

"""

result: list[list[int]] = []

create_all_state(1, n, k, [], result)

return result

def create_all_state(

increment: int,

total_number: int,

level: int,

current_list: list[int],

total_list: list[list[int]],

) -> None:

if level == 0:

total_list.append(current_list[:])

return

for i in range(increment, total_number - level + 2):

current_list.append(i)

create_all_state(i + 1, total_number, level - 1, current_list, total_list)

current_list.pop()

def print_all_state(total_list: list[list[int]]) -> None:

for i in total_list:

print(*i)

if __name__ == "__main__":

n = 4

k = 2

total_list = generate_all_combinations(n, k)

print_all_state(total_list)