# Title: Permutations
# Heading: Python Program to Print All Permutations
# Level: intermediate
# Tags: permutations, backtracking, recursion, orderings, arrangements
# Time: O(n × n!)
# Space: O(n)
# About: Lists every ordering of a list's items by choosing an item for each place in turn, then undoing the choice to try the next one.

def permutations(items):
    """Every ordering of items, as a list of lists."""
    result = []
    current = []
    used = [False] * len(items)

    def backtrack():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, item in enumerate(items):
            if not used[i]:
                used[i] = True        # choose this item
                current.append(item)
                backtrack()           # fill the places after it
                current.pop()         # undo the choice
                used[i] = False

    backtrack()
    return result


for ordering in permutations(["A", "B", "C"]):
    print("".join(ordering))