문제

정보 동아리 회장을 선출하려고 한다.

올해는 단일 후보만 등록하여 찬반 투표를 실시하였다.

n명의 학생이 O, X로 의사 표현을 한다면 나올 수 있는 경우를 모두 출력하시오.

예를 들어 2명이 투표하는 경우 나올 수 있는 경우는

OO

OX

XO

XX

이다.

입력

투표자 수 n이 정수로 입력된다.(1 <= n <= 7)

입력 예시

3

출력

나올 수 있는 모든 경우의 수를 출력한다.

찬성은 알파벳 대문자 O, 반대는 알파벳 대문자 X로 표시한다.

출력 예시

OOO
OOX
OXO
OXX
XOO
XOX
XXO
XXX

풀이

처음에 진행할 때 엄청나게 애를 먹었다.
백트래킹 익숙치 않아서 2일은 고민하고 풀었다.

# 투표자 수
N = int(input())

# 2차원 배열을 무조건적으로 사용해야 가능할 것으로 보임
n_list = [['O','X'] for _ in range(N)]

# Backtracking , 2개의 투표 결과 중에서 선택이 되면 다음으로 넘어가야 함
def generate_combinations(n_list, row, current_combination, combinations):
    if row == len(n_list):
        combinations.append(current_combination.copy())
        return
    
    for value in n_list[row]:
        current_combination.append(value)
        generate_combinations(n_list, row + 1, current_combination, combinations)
        current_combination.pop()

combinations = []
generate_combinations(n_list, 0, [], combinations)

for combination in combinations:
    print(''.join(combination))