backtracking.all_subsequences

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.

Attributes

seq

Functions

create_state_space_tree(→ None)

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

generate_all_subsequences(→ None)

Module Contents

backtracking.all_subsequences.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.

Parameters:

  • sequence – The input sequence for which subsequences are generated.

  • current_subsequence – The current subsequence being built.

  • index – The current index in the sequence.

Example: >>> sequence = [3, 2, 1] >>> current_subsequence = [] >>> create_state_space_tree(sequence, current_subsequence, 0) [] [1] [2] [2, 1] [3] [3, 1] [3, 2] [3, 2, 1]

>>> sequence = ["A", "B"]
>>> current_subsequence = []
>>> create_state_space_tree(sequence, current_subsequence, 0)
[]
['B']
['A']
['A', 'B']

>>> sequence = []
>>> current_subsequence = []
>>> create_state_space_tree(sequence, current_subsequence, 0)
[]

>>> sequence = [1, 2, 3, 4]
>>> current_subsequence = []
>>> create_state_space_tree(sequence, current_subsequence, 0)
[]
[4]
[3]
[3, 4]
[2]
[2, 4]
[2, 3]
[2, 3, 4]
[1]
[1, 4]
[1, 3]
[1, 3, 4]
[1, 2]
[1, 2, 4]
[1, 2, 3]
[1, 2, 3, 4]
backtracking.all_subsequences.generate_all_subsequences(sequence: list[Any]) → None
backtracking.all_subsequences.seq: list[Any] = [1, 2, 3]