백준 15655_N과 M(6) / Python

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

예제 입력 1 

3 1
4 5 2

예제 출력 1 

2
4
5

예제 입력 2 

4 2
9 8 7 1

예제 출력 2 

1 7
1 8
1 9
7 8
7 9
8 9

예제 입력 3 

4 4
1231 1232 1233 1234

예제 출력 3 

1231 1232 1233 1234

---

저번에 푼 15655번 문제랑 중복이 불가능하다는 점만 달라서 combinations를 가져와서 풀었다.

from itertools import combinations
import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

for comb in combinations(nums, m):
  for num in comb:
    print(num, end=' ')
  print()

 

라이브러리없이 백트래킹으로 풀기.

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
arr = [-1 for _ in range(m)]

def backtracking(num, prev):
    if num == m:
        print(" ".join(str(x) for x in arr))
        return
  
    for i in range(prev, n):
        arr[num] = nums[i]
        backtracking(num + 1, i+1) #중복제외 니까 i가 아닌 i+1

backtracking(0, 0)

메모리, 시간 동일