in this problem we want to determine all possible subsequences of the given sequence we use backtracking to solve this problem time complexity o2n where n denotes the length of the given sequence 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 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
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:
    

    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)