FilesExpand file tree

Write-for-current-Python

/

all_subsequences.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (30 loc) · 1.12 KB

Write-for-current-Python

/

all_subsequences.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (30 loc) · 1.12 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

"""

In this problem, we want to determine all possible subsequences

of the given sequence. We use backtracking to solve this problem.

Time complexity: O(2^n),

where n denotes the length of the given sequence.

"""

from typing import Any, List

def generate_all_subsequences(sequence: List[Any]) -> None:

create_state_space_tree(sequence, [], 0)

def create_state_space_tree(

sequence: List[Any], current_subsequence: List[Any], index: int

) -> None:

"""

Creates a state space tree to iterate through each branch using DFS.

We know that each state has exactly two children.

It terminates when it reaches the end of the given sequence.

"""

if index == len(sequence):

print(current_subsequence)

return

create_state_space_tree(sequence, current_subsequence, index + 1)

current_subsequence.append(sequence[index])

create_state_space_tree(sequence, current_subsequence, index + 1)

current_subsequence.pop()

if __name__ == "__main__":

seq: List[Any] = [3, 1, 2, 4]

generate_all_subsequences(seq)

seq.clear()

seq.extend(["A", "B", "C"])

generate_all_subsequences(seq)