N과 M (2) 백준 15650번 백트래킹

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

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다. 지난번 N과 M 1은 모든 조합을 구했다면 이번에는 오름차순으로 구하는 문제입니다. 이것도 isused 배열을 약간만 조작하면 금방 구할 수 있습니다.

---

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+1] = [True]*(j+1)
            func(k+1)
            isused[0:j+1] = [False]*(j+1)

func(0)

결국 오름차순 이기 때문에 2를 사용했다면 1도 사용하지 못하고 또는 3을 사용했다면 1,2,3 모두 사용하지 못합니다.

그래서 어떤 값을 사용했다면 그것보다 작은 나머지 값들도 모두 True/False처리를 하면 됩니다.

j+1까지인이유는 파이썬리스트에서 0:j를 하면 j를 포함하지 않습니다.