[백준] 15650번 N과 M(2) (bk_15650)

N과 M(2) - 15650번

문제

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

예제 입출력

# 입력
4 2
# 출력
1 2
1 3
1 4
2 3
2 4
3 4

생각한 알고리즘

• 백트래킹

## 백트래킹
# 입력
N, M = map(int, input().split())

orders = []
for i in range(M):
    orders.append(0)
# 백트랙킹 함수
def back(idx,order_list):
    ord_list = order_list[:]
    if(idx >= M):
        # 완성된 수열 출력
        for i in range(M-1):
            print(ord_list[i],end = " ")
        print(ord_list[M-1])
    else:
        st = 1 if (idx == 0) else order_list[idx-1] + 1
        for i in range(st ,N+1):
            # 이전 idx 위치의 배열 값보다 큰 값 할당
            if(not i in order_list):
                ord_list[idx] = i
                back(idx + 1, ord_list)

back(0,orders)