N과 M (4) 백준 15652번 백트래킹

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

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

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

이번에는 같은 수를 여러번 골라도 되지만 비내림차순을 만족해야합니다.

그래서 2를 선택한다면 1만 True/False를 체크하고 2는 그대로 두는식으로 진행하면 됩니다.