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

문제 파악

어제 풀었던 N과 M (1) 문제에 이어 두번째 백트래킹 문제이다.

문제는 거의 동일하되, 여기서는 1 2 와 2 1 를 같은 수열로 본다.
중복을 제거해야하니 set() 자료형을 이용하면 될 것 같았지만 아니었다.

핵심은 중복을 제거하는 것이 아니라 오름차순을 유지하는 것.

해답 및 풀이

import sys
input = sys.stdin.readline

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

# nums = [1,2,...,N]
nums = []
for i in range(N):
    nums.append(i+1)

path = []

def backtracking(start):
    # 종료 조건
    if len(path) == M :
        print(*path)
        return # 백트래킹
    
    # i를 start부터 시작해야  이전보다 항상 커짐 -> 오름차순
    for i in range(start,N):
        path.append(nums[i])
        backtracking(i+1) # 다음 호출은 i+1 부터
        path.pop()

backtracking(0)

set()은 이미 생성된 데이터에서 중복된 값을 제거할 때 쓰는 자료형이지,
백트래킹 단계에서 "중복을 만들지 않도록 탐색을 제한"할 때는 쓰지 않는다.

백트래킹은 탐색 규칙을 내가 직접 짜는 알고리즘이라
애초에 중복된 조합이 생성되지 않게 루프 범위를 제어해야 한다.

range(start,M) 을 해준 후 start를 1씩 증가시키는 식으로 오름차순을 유지할 수 있었다.