BOJ 15654 - N과 M(5) (Python)

S3, 백트래킹

문제

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

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

풀이

• 백트래킹(dfs) 풀이를 거의 안해봐서 공부 시작
• 이론적 이해를 조금 더 해야할 거 같다.

from sys import stdin
n, m = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))

arr.sort()
visited = [0] * n
out = []

def backtracking(depth, n, m):
    if depth == m:
        print(*out)
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = 1
            out.append(arr[i])
            backtracking(depth + 1, n, m)
            out.pop()
            visited[i] = 0

backtracking(0, n, m)