[백준] #15663 N과 M (9) - 파이썬

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1
4 4 2

예제 출력 1 복사

2
4

예제 입력 2 복사

4 2
9 7 9 1

예제 출력 2 복사

1 7
1 9
7 1
7 9
9 1
9 7
9 9

---

복기

1. 아직 백트래킹이 익숙치 않는데 내부적으로 돌아가는것을 반복숙달하자.

정렬된 입력: ls = [1, 7, 9, 9]

시작: backtrack(0) (depth = 0)
i = 0 → ls[0] = 1
seq = [1]

→ backtrack(1)로 들어감

i = 1 → ls[1] = 7
seq = [1, 7]

depth = 2 → 출력: 1 7

seq.pop() → seq = [1] 복원

i = 2 → ls[2] = 9
seq = [1, 9]

출력: 1 9

seq.pop() → seq = [1]

i = 3 → ls[3] = 9 (이건 prev와 같아서 skip)
❌ 중복이라 패스

이제 seq = [1]인데
그다음도 없으므로 seq.pop()으로 1 제거 → seq = []

그다음 i = 1 → ls[1] = 7
seq = [7]

→ backtrack(1)

i = 0 → ls[0] = 1 (방문 안 했음)
seq = [7, 1]

출력: 7 1

seq.pop() → seq = [7]

i = 2 → ls[2] = 9
seq = [7, 9]

출력: 7 9

seq.pop() → seq = [7]

i = 3 → ls[3] = 9 (중복이니까 skip)
seq.pop() → seq = []

2. 이때 seq랑 visited 리스트는 재귀가 끝나면 pop()과 False로 상태를 유지해줘서 재귀 함수 안에서도 유지가 된다. 

---

솔루션

N, M = map(int, input().split()) # M은 수열의 타겟 길이
ls = list(map(int, input().split()))

ls.sort()
visited = [False] * len(ls)

seq = []

def backtrack(depth): # depth는 수열의 몇번째 숫자
    if depth == M: # 종료 조건
        print(*seq)
        return
    prev = 0
    for i in range(N):
        if not visited[i] and prev != ls[i]:
            visited = True
            seq.append(ls[i])
            prev = ls[i]
            backtrack(depth+1)
            seq.pop()
            visited[i] = False

backtrack(0)