[백준/15650/파이썬] N과 M (2)

---

소스코드

n,m = list(map(int,input().split()))

s = []

def dfs(start):

    if len(s)==m:     

        print(' '.join(map(str,s)))

        return

    

    for i in range(start,n+1):

        if i not in s:

            s.append(i)

            dfs(i+1)

            s.pop()

dfs(1)

---

알고리즘

파이썬에 있는 기능인 itertools의 permutation을 사용해서 풀면 될 것 같았으나 문제의 취지에 맞게 백트래킹을 이용해서 풀려고 했다.

1부터 시작해서 s에 담고 for문을 돌면서 s에 포함되지 않은 애들을 삽입해 나가는 dfs 알고리즘이다. 그리고 조건을 만족하면 출력하고 다음 수열을 찾는다.