알고리즘 - 백트리킹 (15469 - N과 M(1))

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

---

문제 요약

N과 M을 받아 1~N까지의 갯수중 M개를 뽑는 조합

 

 

접근 방법

같은 수가 됐을때 출력을 해야하고, 몇개를 선택해야 할지 모른다.

따라서 재귀로 여러번 불러 개수를 채울때 출력

같은 수를 선택하면 안되므로 선택한지를 확인하는 플래그 배열 선언으로 해결

 

 

N, M = map(int, input().split())
stack = list()
isDone = [False for i in range(8)]
def combin(count):
    global stack
    if count == M:
        print(' '.join(stack))
        return
        
    for i in range(N):
        stack.append(str(i+1))
        if not isDone[i]:
            isDone[i] = True   
            combin(count+1)
            isDone[i] = False
        stack.pop()
 
combin(0)