[수학] 백준 15649번 N과 M(1) with python

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

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

pair = []

def btracking(n, m, pair):
    if len(pair) == m :
        print(' '.join(map(str,pair)))
        return

    for i in range(1, n+1):
        if i not in pair:
            pair.append(i)
            btracking(n, m, pair)
            pair.pop()

btracking(n, m, pair)

굉장히 유명한 문제 중 하나인 n과 m!
하지만 푸는 방법을 모르겠어서 이 문제는 그냥 조금만 고민하다가 구글링 해봤다...ㅎ
알고리즘 중에서 백트래킹 방법을 사용해야했던 문제였다. (스터디에 정리할 예정)
[1, 2, 3, 4] 에서 4개 뽑는 예시로 설명하자면
pair이라는 리스트를 만들어 한개 한개씩 넣다가 4개가 되면 함수를 종료하는 재귀적으로 돌아가게 되어있는 코드이다.

1. 1번째 bt 실행 pair = [1]
2. 2번째 bt 실행 pair = [1, 2]
3. 3번째 bt 실행 pair = [1, 2, 3]
4. 4번째 bt 실행 pair = [1, 2, 3, 4]
5. 5번째 bt 실행, pair의 길이 4, 5번째 bt 종료
6. 다시 4번째 bt 마저 실행, 4를 pop, 4번째 bt 종료, pair = [1, 2, 3]
7. 다시 3번째 bt 마저 실행, 3을 pop, pair에 4가 없으므로 pair = [1, 2, 4], 4번째 bt 실행
8. ...

이런식으로 실행되게 된다.
N과 M 시리즈는 굉장히 많은것으로 알고있는데 1번째는 중복을 허용한 ([1, 2, 3, 4]와 [1, 2, 4, 3]을 다른 것이라고 봄) 문제였다.
굳!!

 

참고한 블로그 : https://jiwon-coding.tistory.com/21