새싹프로그래머의 이야기

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

처음 보는 백트래킹 문제라, 고민고민 하다가 결국 풀지 못하고 백트래킹에 대해서 구글링해서 푼 문제입니다.

DFS와 다르게 되돌아간다는 개념이 정말 신기하게 다가왔던 문제였습니다.

문제: 두 개의 수 N,M이 주어졌을 때, 1부터 N까지 자연수 중 M개의 수로 구성할 수 있는 모든 오름차순 수열을 모두 구하는 문제입니다.

풀이 방법: 백트래킹

풀이 코드:

import sys

n, m = map(int,sys.stdin.readline().rstrip().split())

lst = []

def backTracking(start):
    if len(lst) == m:
        print(' '.join(map(str,lst)))
        return

    for i in range(start,n+1):
        if i not in lst:
            lst.append(i)
            backTracking(i+1)
            lst.pop()

backTracking(1)