[Python] 백준 15650 N과 M 2

🧑‍💻 [Python] 백준 15650 N과 M 2

Silver 3 - Backtracking

쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다

하지만 Backtracking을 공부하고 싶어서 풀었던 문제다

• 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다
  • 안 만들면 무한 루프
• 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다
  • 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다
  • 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다
  • 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터 for문을 순회한다
• 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다

---

 

코드

 

백트래킹 사용

N, M = map(int, input().split())

nums = []

def backtracking(start):

    if len(nums) == M:
        print(' '.join(map(str, nums)))
        return

    for num in range(start, N + 1):
        if num not in nums:
            nums.append(num)
            backtracking(num + 1)
            nums.pop()

backtracking(1)

 

combinations 사용

from itertools import combinations

N, M = map(int, input().split())

num_list = [num for num in range(1, N + 1)]

for nums in combinations(num_list, M):
    print(" ".join(map(str, list(nums))))