[백준/python] 6443 애너그램

import sys
input = sys.stdin.readline

def backtrack(idx=0, result=""):
    # 백트래킹 종료 조건
    if idx==len(s):
        return print(result)
    
    for i in data:
        # 데이터가 남아있다면
        if data[i]:
            data[i] -=1
            # result에 더하기
            backtrack(idx+1, result+i)
            data[i] +=1

for _ in range(int(input())):
    s = sorted(input().strip())
    # 중복 제거 및 개수 계산을 위한 딕셔너리 활용
    data = dict()
    for char in s:
        data[char] = data.get(char,0)+1
    backtrack()

백트래킹

중복을 허용하지 않고 모든 나올 수 있는 애너그램을 만드는 문제입니다.
문제 자체는 N과 M (9) 문제와 비슷하다고 생각해서 같은 방식으로 접근했으나, 시간 초과가 발생했습니다.

문자열의 길이가 최대 20이기 때문에 같은 방식으로 문제 풀이가 불가능함을 깨닫고, 딕셔너리를 활용해 data변수에 각 문자의 개수를 순서대로 저장해두고, 백트래킹을 통해 남은 개수를 관리하는 방식을 사용했습니다.