[Python] 백준 15650, 15649 -백트래킹 알고리즘

백준 15649

nPm 순열을 구해주면 된다

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
chk = [False]*(n+1) # 인덱스 0 사용 x

re = []
def recur(num):
    if num == m:  # 실수했음
        print(' '.join(map(str, re)))
        return

    for i in range(1,n+1):  # 1부터 시작이지 n+1까지 범위 늘려야함
        if (chk[i] == False):
            chk[i] = True
            re.append(i)
            recur(num+1)
            chk[i]=False
            re.pop()

recur(0)

 

 

백준 156450

위 문제처럼 순열을 구하는건데, 중복된 내용만 제거하면 된다.

import sys

input = sys.stdin.readline
n,m = map(int, input().split())
re = []

def recur(num):
    if m == len(re) :  # 수열 조건이 만족됐을 때
        # 정렬해서 리스트에 추가
        #tmp = set(re)
        print(' '.join(map(str,re)))
        return

    for i in range(num,n+1):
        if i not in re :
            re.append(i)
            recur(i+1)
            re.pop()

recur(1)