[백준] 15654 - N과 M (5) (백트래킹, permutations)

algorithm'''problem solve

[백준] 15654 - N과 M (5) (백트래킹, permutations)

JunHwa Park 2020. 10. 26. 18:34

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

15654번: N과 M (5)

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

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from itertools import permutations
 
n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
 
# for perm in permutations(arr, m):
#     for i in perm:
#         print(i, end=' ')
#     print()
 
 
def backtracking(li):
    if len(li) == m:
        for i in li:
            print(i, end=' ')
        print()
    elif len(li) > len(arr):
        return
 
    for i in range(0, n):
        if arr[i] not in li:
            backtracking(li + [arr[i]])
 
 
backtracking(list())

cs

중복 없는 순열을 구하는 문제이다.

파이썬으로는 permutations를 이용해서 간단히 구현할 수 있고(주석), 세부 로직은 아래 코드와 같다.