[백준] 15650번 N과 M (2)

💡문제접근

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제이다. combinations을 이용해서 간단히 해결할 수 있었다.

💡코드(메모리 : 30616KB, 시간 : 36ms)

from itertools import combinations

N, M = map(int, input().split())
arr = [i for i in range(1, N+1)]

for i in combinations(arr, M):
    print(*i)

📌백트래킹 풀이 방법(메모리 : 31256KB, 시간 : 44ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
li = []

def recursive(start):
    if len(li) == M:
        print(" ".join(map(str, li)))
        return 0
    else:
        for i in range(start, N+1):
            if i not in li:
                li.append(i)
                recursive(i + 1)
                li.pop()

recursive(1)

• [[백준] 15649번 N과 M (1)] 문제와 다른 점은 순서의 체크 유무다. 앞선 문제는 (1, 2), (2, 1) 두 순서쌍은 서로 다른 순서쌍으로 취급했지만 현재 문제는 두 순서쌍은 같은 순서쌍으로 취급한다는 점이다. start라는 변수를 추가해줬다.

💡소요시간 : 1m