재귀로 순열 만들기 + 재귀 핵심

1. "내가 하는 일"을 한 문장으로 정리

함수 하나가 어떤 역할을 하는지 명확히 정의하세요.

예시:

generatePermutations() → "현재 상태에서 가능한 모든 순열을 만들어낸다"

2. 기저 조건(Base Case)을 먼저 정하기

재귀가 끝나야 할 조건을 먼저 만들어야 무한 루프에 빠지지 않아요.

예시:

if (current.size() == nums.length) { System.out.println(current); return; }

3. "작은 문제로 줄이는 방법"을 생각하기--->이걸 작은 함수로 정의한다(한개씩 넣어주기)

재귀는 항상 문제를 조금 더 작게 나눠서 해결해요.

예시:

[1, 2, 3]의 순열을 만들기 위해, 1을 고정하고 나머지 [2,3]의 순열을 재귀로 만든다

4. 백트래킹(backtracking)을 기억하자

한 번 선택한 걸 다시 되돌리는 과정이 꼭 필요해요.

예시: current.remove(current.size() - 1); // 선택을 취소 visited[i] = false; // 다시 사용할 수 있게 표시

5. 먼저 작은 예제로 종이에 그려보기

종이에 n = 2 또는 n = 3만 넣어서 어떻게 함수가 호출되는지 흐름을 적어보면 진짜 이해가 빨라져요.

예:

nums = [1, 2]
current = []

1 선택 -> [1]
	2 선택 -> [1,2] 출력
	→ 되돌리기: [1] → []

2 선택 -> [2]
	1 선택 -> [2,1] 출력

한 문장 요약

**"재귀는 나 대신 작은 문제를 해결해줄 함수 하나를 믿고 부른다"**는 마인드로 접근하세요.

 

실수 조심 -> 백 트래킹 위치

✅ 정리

조건설명

for문 안에서 백트래킹	보통 선택지가 여러 개인 문제 (순열, 조합, N-Queen)
for문 없이 백트래킹	트리 탐색, 경로 탐색 등 구조가 고정돼 있을 때 사용

순열에서 백트래킹이 for문 안에서 일어나는 이유

 

📌 다시 보기: 핵심 원칙

if (기저 조건)은 맨 위에	더 이상 쪼갤 수 없거나, 작업이 끝났다면 더 이상 재귀하지 않고 종료
for문, 재귀 호출은 그 아래	아직 해야 할 작업이 남았을 때 작은 문제로 분할해서 재귀

예시

void dfs(int node, boolean[] visited) {
    if (visited[node]) return;  // ✅ 이미 방문했으면 종료
    visited[node] = true;       // 현재 노드 방문 처리

    for (int next : graph[node]) {
        dfs(next, visited);     // 🔁 인접 노드 재귀적으로 탐색
    }
}