문제

<예제>
3 1				1
				2
                3

4 2				1 2
				1 3
                1 4
                2 3
                2 4
                3 4

풀이

1. s라는 리스트를 만들고 길이가 M이되면 print
2. range(1, N+1)에서 i를 append 후 i+1 재귀 실행
3. 실행 후 pop   <- 이 부분이 헷갈렸음

N, M = map(int, input().split())
s = []

def back(start):
    if len(s) == M:                     # 길이가 M이면 출력
        print(' '.join(map(str, s)))

    for i in range(start, N+1):
        if i not in s:              # i가 리스트에 없으면 추가
            s.append(i)             # 재귀 실행
            back(i+1)
            s.pop()


back(1)

백트래킹(Backtracking) - 퇴각검색

• 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행

• 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.

• DFS(깊이 우선 탐색) 기반

• Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.

• Pruning : 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다.

- 해를 구하는 도중 해가 아니어서 막히면 막히기 전으로 다시 돌아가서 해를 찾는 기법
- 예를 들어, 갈랫길에서 한쪽으로 갔다가 이 길이 아닌 것 같으면 왔던 길로 되돌아와 다른 선택지로 간다고 생각하면 된다.
- 가상의 트리에서 해를 구하기 위해 부모 노드에서 자식 노드까지 뻗어나간다. - 만약 해당 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아간다.
- 해가 아닌 선택지는 없애면서 탐색하기 때문에 시간복잡도를 줄일 수 있다.

백트랙킹 구현
퇴각검색