[백준] 15655 N과 M(6) 파이썬

문제집 출처 :: 백준 N과 M https://www.acmicpc.net/workbook/view/2052

 

이전글

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15649. N과 M (1) 파이썬

2020/03/02 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15650 N과 M(2) 파이썬

2020/03/03 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15651-15652. N과 M(3)-(4) 파이썬

2020/03/08 - [파이썬 코딩테스트/BAEK JOON] - [백준] 15654 N과 M(5) 파이썬

 

---

문제출처 https://www.acmicpc.net/problem/15655

[백준] 15655 N과 M(6) - 파이썬 DFS 재귀

문제

N개의 자연수와 자연수 M이 주어졌을 때,

아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

N개의 자연수는 모두 다른 수이다.

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

• 고른 수열은 오름차순이어야 한다.

입력

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

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

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

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

 

예제 입력	예제 출력
3 1  4 5 2	2 4 5
4 2 9 8 7 1	1 7 1 8 1 9 7 8 7 9 8 9
4 4 1231 1232 1233 1234	1231 1232 1233 1234

 

입력 [1,7,8,9] 중 2개 뽑음, 순서가 의미 없음, 출력 [1,7] == [7,1] 같아서 하나만 [1,7] 출력

---

<풀이 PASS>

 

# N과 M (6) N 개 중 M 뽑기, 중복안됨
 
n,m = map(int,input().split())
numbers = list(map(int,input().split())) # 1~n까지
numbers.sort()
is_number = [0 for _ in range(m)] # 출력 개수
check = [False for _ in range(len(numbers))] # 사용여부(씀=True, 안씀= False)
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,len(numbers)):
        #숫자를 사용 안했다면
        if not check[i]:
            #나는 i 번째 숫자를 사용하겠어
            check[i] = True
            #숫자를 배치하겠어
            is_number[idx] = numbers[i]
            # 다음은 알아서 재귀해~
            dfs(idx+1,i+1) # 나 다음 인덱스 부터 ~
            #사용다했어
            check[i] = False
dfs(0,0)