[BOJ/백트래킹] N과 M (2)

문제링크 : https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

풀이

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

answer = [0]*m
def backtracking(L,s):

    # 길이가 m이라면 출력
    if L == m:
        for j in answer:
            print(j,end = " ")
        print()
        return
    # s부터 n+1까지 반복문
    for i in range(s,n+1):
        answer[L] = i  # answer의 인덱스 위치에 i 넣기
        backtracking(L+1, i+1) # 같은 수를 허락하지 않으므로 i+1


backtracking(0,1)

1. answer이라는 리스트에 L의 인덱스에 s를 넣어주는 구조이다
2. backtracking(0,1) 로 시작하면 answer[0] = 1 의 값을 넣어주고 또 다시 backtracking 함수가 돌아간다 (1,2) → (2,3)
3. L이 m이 되면은 answer의 값이 다 채워졌으므로 return을 통해 출력하고 재귀함수를 탈출한다
4. (0,1)일때 s를 반복문을 돌리므로 (0,2) (0,3),(0,4)을 반복한다.
5. 마찬가지로 (1,2) 일때도 (1,3) ,(1,4)를 반복하여 L = m이 될때 값을 출력한다.

위와 같은 문제를 조합이라고 한다. 수열에서는 순열과 조합이 있다.

순열 : 순서가 의미가 있는 경우 (1,2) ≠ (2,1)

조합 : 순서가 의미 없는 경우 (1,2) = (2,1)