[백준 15654] N과 M (5)

문제

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

• N개의 자연수 중에서 M개를 고른 수열

 

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

출력

한 줄에 선택한 M개의 수를 나열한다.

---

접근

M개의 수를 선택하기위해 백트래킹을 사용하였고 선택할 수를 찾는 인덱스를 0부터 시작하여 찾도록 하였다.

 

구현

아직 선택하지 않은 수 중에서 숫자를 선택할 때 처음부터 탐색을 하도록 하였다.

왜냐하면 (1, 7)과 (7, 1)은 다른 조합이기 때문에 이 두 개의 조합도 출력하도록 하였다.

def select(next, picked):
    if len(picked) == M:
        print(*picked)

    for idx in range(N):
        if not visited[idx]:
            visited[idx] = True
            picked.append(numbers[idx])
            select(idx+1, picked)
            visited[idx] = False
            picked.pop()