📘[15654] N과 M (5)

문제

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

예제 입력 1

4 2
9 8 7 1

예제 출력 1

1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

예제 입력 2

4 4
1231 1232 1233 1234

예제 출력 2

1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231

답안

import sys 

input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

arr = [i for i in range(1, n+1)]
result = []

def dfs(node):
    if len(result) == m:
        print(*result)
        return
    
    for i in nums:
        if i in result:  # 중복제거
            continue
        result.append(i)
        dfs(i)
        result.pop()

dfs(0)

풀이

N과 M (4)와 거의 유사하다.

그냥 재귀를 실행하기 전에, 각 요소를 돌면서 중복만 제거해주면 된다.

우선 기존과 다르게 1부터 시작되는 숫자를 선택하는게 아니라, 숫자를 입력하니까 for i in nums로 nums를 순회했음.

또 여기서 if i in result: continue를 통해 중복된 경우에는 무시하고 넘어가도록 해서 중복을 제거함.

회고

• 요소의 중복을 허용하지 않는 순열은 없을까?