in this problem we want to determine all possible permutations of the given sequence we use backtracking to solve this problem time complexity on n 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 lensequence index children it terminates when it reaches the end of the given sequence remove the comment to take an input from the user printenter the elements sequence listmapint input split creates a state space tree to iterate through each branch using dfs we know that each state has exactly len sequence index children it terminates when it reaches the end of the given sequence remove the comment to take an input from the user print enter the elements sequence list map int input split
from __future__ import annotations


def generate_all_permutations(sequence: list[int | str]) -> None:
    create_state_space_tree(sequence, [], 0, [0 for i in range(len(sequence))])


def create_state_space_tree(
    sequence: list[int | str],
    current_sequence: list[int | str],
    index: int,
    index_used: list[int],
) -> None:
    

    if index == len(sequence):
        print(current_sequence)
        return

    for i in range(len(sequence)):
        if not index_used[i]:
            current_sequence.append(sequence[i])
            index_used[i] = True
            create_state_space_tree(sequence, current_sequence, index + 1, index_used)
            current_sequence.pop()
            index_used[i] = False




sequence: list[int | str] = [3, 1, 2, 4]
generate_all_permutations(sequence)

sequence_2: list[int | str] = ["A", "B", "C"]
generate_all_permutations(sequence_2)