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

문제집 출처 :: 백준 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) 파이썬

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

---

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

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

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

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

출력

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

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

 

예제 입력	예제 출력
3 1  4 5 2	2 4 5
4 2 9 8 7 1	1 1 1 7 1 8 1 9 7 1 7 7 7 8 7 9 8 1 8 7 8 8 8 9 9 1 9 7 9 8 9 9

 

 

입력 [1,7,8,9] 중 2개 뽑음, 같은걸 다시 뽑을 수 있음. 순서가 의미 있음, 출력 [1,7] != [7,1] 달라서 둘 다 나옴 

[7,7] == [7,7] 은 한 번으로 됨

---

<풀이 PASS>

 

 
# # 7번. [백준] 15656
# #  n 갯수들 중에 m 개 뽑기. 중복사용가능. 순서있음. [1,2],[2,1] 다르게 봄
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(n)] # 사용여부 필요없음
def dfs(idx,next):
    if idx >= m: # 0부터 m출력개수 되면
        print(*is_number)
        return
    for i in range(next,n):
        is_number[idx] = numbers[i]
        dfs(idx+1,next)
dfs(0,0)