백준 boj 15663 - N과 M(9) (파이썬, python)

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

 

백트래킹을 이용하는 기본 문제였다.

다만, 중복에 관한 제약조건들이 있었는데

자기 자신을 출력하면 안되고, 이미 출력한 조합은 다시 출력해서는 안 된다.

 

자기 자신에 대한 여부는 visited 라는 배열로 관리하였고,

이미 출력한 것에 대한 여부는 printed 라는 배열을 통해 출력한 것들을 저장하여 비교해주었다.

 

code

 

n, m = map(int,input().split())
input_list = list(map(int, input().split()))
input_list.sort()
visited = [0] * n
printed = []
ans = []

def dfs(iter):
    if iter == m:
        if ''.join(map(str, ans)) not in printed: # 출력 여부
            printed.append(''.join(map(str, ans)))
            print(*ans)
            return
    for i in range(n):
        if not visited[i]: # 자기 자신, 출력 여부에서 else가 없어도 되는 이유이기도 하다.
            ans.append(input_list[i])
            visited[i] = 1
            dfs(iter + 1)
            ans.pop()
            visited[i] = 0
dfs(0)