N과 M (8) 백준 15657번 백트래킹

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

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

n,m = map(int,input().split())
num_list = list(map(int,input().split()))
num_list.sort()
arr = [0]*m
isused = [False]*(max(num_list)+1)
def func(k):
    if k==m:
        for i in range(m):
            print(arr[i], end=' ')
        print()
        return
    for j in num_list:
        if not isused[j]:
            arr[k]=j
            isused[0:j] = [True]*(j)
            func(k+1)
            isused[0:j] = [False]*(j)
func(0)

설명생략..