백트래킹- 조합 구현

문제

1이상 N 이하의 숫자 중 M 개의 숫자를 골라 만들 수 있는 모든 조합을 구해주는 프로그램을 작성

---

코드

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

combination = []
def print_combination():
    for elem in combination:
        print(elem, end = " ")
    
    print()

def find_combination (cnt,last_num):
    if cnt==m:
        print_combination()
        return

    #뽑을 수 있는 원소의 후보들 탐색
    for i in range(last_num+1,n+1):
        combination.append(i)
        find_combination(cnt+1,i)
        combination.pop()


# 가능한 범위를 순회하며 해당 숫자가 
# 조합의 첫번째 숫자일 때를 탐색
for i in range(1, n + 1):
    combination.append(i)
    find_combination(1, i)
    combination.pop()

ex ) 5,3

i=1 일때 backtraking으로 pop과 append 를 반복하며 

1 

1 2 

1 2 3

1 2 

1 2 4 

1 2 

1 2 5

...

이러한 순서로 진행된다.