[백준/Python]15654: N과 M (5)

문제

https://www.acmicpc.net/problem/15654
백준 문제집 - 0x0C강 - 백트래킹

 

알고리즘: 백트래킹

---

풀이

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

 

백트래킹으로 순열(permutation)을 만드는 문제다.
순열은 n개의 숫자 중에서 순서를 고려하여 r개를 뽑는 경우의 수를 말한다.

permutations 모듈을 사용하면 더 간단하겠지만, '백트래킹' 알고리즘 문제니까 정석대로 풀었다ㅋㅋ

 

전체 코드

# 메모리: 31120KB / 시간: 152ms
from sys import stdin


input = stdin.readline

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))

def backtrack(ret):
    if len(ret) == M:
        print(" ".join(map(str, ret)))
        return

    for i in range(N):
        if nums[i] in ret:
            continue
        ret.append(nums[i])
        backtrack(ret)
        ret.pop()

backtrack([])

 

먼저 빈 리스트를 넣어 함수를 실행하고, 길이가 M이 될때까지 숫자를 append한다.
단, 숫자가 중복되면 안되므로 만약 현재 숫자가 이미 리스트에 존재한다면 넘어간다.

또한 결과값을 오름차순으로 출력해야하기 때문에 함수 실행 전에 숫자 리스트를 정렬해줘야 한다.