p

```
"""
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 __future__ import annotations
from typing import Any
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.
:param sequence: The input sequence for which subsequences are generated.
:param current_subsequence: The current subsequence being built.
:param 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]
"""
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] = [1, 2, 3]
generate_all_subsequences(seq)
seq.clear()
seq.extend(["A", "B", "C"])
generate_all_subsequences(seq)
```