백트래킹(BackTracking)

✅ 순열 (Permutation)

                 [ ]
          /       |       \
       [1]       [2]       [3]  
      /   \     /   \     /   \  
  [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]  <-- 모든 리프 노드 (완성된 순열)
  
✔ 각 단계에서 숫자를 하나 선택하고, 탐색을 진행한 후 원래 상태로 되돌리는 과정(Backtracking)이 반복됩니다.
✔ 탐색 깊이에 따라 들여쓰기를 조절하여 트리 형태로 출력됩니다.

 

◈ 코드 예제 1

- `n`, `r` 이 주어진 경우

import java.util.*;

public class PermutationGenerator {

    public static List<List<Integer>> permute(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];  // 1부터 n까지 숫자를 사용하기 위해 크기를 n+1로 설정
        backtrack(n, r, new ArrayList<>(), visited, ans);
        return ans;
    }

    private static void backtrack(int n, int r, List<Integer> curr, boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));  // 정답 저장
            return;
        }

        for (int i = 1; i <= n; i++) {  // 1부터 n까지 숫자 직접 사용
            if (!visited[i]) {  // 방문하지 않은 숫자만 선택
                curr.add(i);
                visited[i] = true;
                backtrack(n, r, curr, visited, ans);
                curr.remove(curr.size() - 1);  // Backtracking: 원래 상태로 되돌리기
                visited[i] = false;  // 방문 체크 해제
            }
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int r = 2;
        List<List<Integer>> result = permute(n, r);
        for (List<Integer> p : result) {
            System.out.println(p);
        }
    }
}

 

◈ 코드 예제 2

- `nums`, `r` 이 주어진 경우

import java.util.*;

public class PermutationWithArray {

    public static List<List<Integer>> permute(int[] nums, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(r, new ArrayList<>(), nums, visited, ans);
        return ans;
    }

    private static void backtrack(int r, List<Integer> curr, int[] nums, boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                curr.add(nums[i]);
                visited[i] = true;
                backtrack(r, curr, nums, visited, ans);
                curr.remove(curr.size() - 1);
                visited[i] = false; // Backtracking: 원래 상태로 되돌리기
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int r = 2;
        List<List<Integer>> result = permute(nums, r);
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }
}

---

✅ 조합 (Combination) 

                   [ ]
          /         |      \       
       [1]         [2]     [3]      
      /   \         |       |    
  [1,2]   [1,3]   [2,3]   [3,4]
      |     |       |       |
 [1,2,3] [1,2,4] [1,3,4]  [2,3,4]  <-- 모든 리프 노드 (완성된 조합)

✔ 각 단계에서 숫자를 하나 선택하고, 다음 선택은 현재 숫자 이후의 숫자만 고려해야 합니다.
✔ 탐색을 진행한 후 원래 상태로 되돌리는 과정(Backtracking)이 반복됩니다.

 

◈ 코드 예제 1

import java.util.*;

public class Combination {

    public static List<List<Integer>> combine(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, r, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int n, int r, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr)); // 정답 저장
            return;
        }

        for (int i = start; i <= n; i++) { // 중복 방지를 위해 `start`부터 탐색
            curr.add(i);
            backtrack(i + 1, curr, n, r, ans); // 다음 숫자는 현재 숫자보다 커야 함
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int r = 2;
        List<List<Integer>> result = combine(n, r);
        for (List<Integer> comb : result) {
            System.out.println(comb);
        }
    }
}

 

◈ 코드 예제 2

import java.util.*;

public class Combination {

    public static List<List<Integer>> combine(int[] nums, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, r, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int[] nums, int r, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr)); // 정답 저장
            return;
        }

        for (int i = start; i < nums.length; i++) { // 중복 방지를 위해 `start`부터 탐색
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums, r, ans); // 다음 숫자는 현재 숫자보다 커야 함
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30, 40};
        int r = 2;
        List<List<Integer>> result = combine(nums, r);
        for (List<Integer> comb : result) {
            System.out.println(comb);
        }
    }
}

---

✅ 부분집합 (Subset) 

                 [ ]
          /               \
       [1]                 []  
      /    \            /      \  
  [1,2]    [1]        [2]       []
  /   \    /   \      /   \    /  \
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] <-- 모든 리프 노드 (완성된 부분집합)

 

◈ 코드 예제 1

import java.util.*;

public class Subsets {

    public static List<List<Integer>> subsets(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int n, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(curr)); // 현재 부분집합을 저장

        for (int i = start; i <= n; i++) { // 숫자를 하나씩 추가하며 탐색
            curr.add(i);
            backtrack(i + 1, curr, n, ans); // 다음 숫자를 선택
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int n = 3;
        List<List<Integer>> result = subsets(n);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

 

◈ 코드 예제 2

import java.util.*;

public class SubsetsWithArray {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr, int[] nums, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(curr)); // 현재 부분집합을 저장

        for (int i = start; i < nums.length; i++) { // 숫자를 하나씩 추가하며 탐색
            curr.add(nums[i]);
            backtrack(i + 1, curr, nums, ans); // 다음 숫자를 선택
            curr.remove(curr.size() - 1); // Backtracking: 원래 상태로 되돌리기
        }
    }

    public static void main(String[] args) {
        int[] nums = {10, 20, 30};
        List<List<Integer>> result = subsets(nums);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

---

✅ 백트래킹(BackTracking), 프루닝(Pruning)

◈ 백트래킹 (BackTracking)

void backtrack(List<Integer> path) {
    if (isFinished(path)) {  // 종료 조건 만족
        answers.add(new ArrayList<>(path));  // 현재 경로 저장
        return;
    }

    for (int choice : getChoices(path)) {  // 가능한 모든 선택
        path.add(choice);  // 현재 선택 추가
        backtrack(path);   // 다음 단계 탐색
        path.remove(path.size() - 1);  // 원래 상태로 되돌리기 (Backtracking)
    }
}

 

◈ 프루닝 (Pruning)

- 조건을 만족하지 않는 경우는 미리 제거

void backtrack(List<Integer> path) {
    if (isFinished(path)) {  // 종료 조건 만족
        answers.add(new ArrayList<>(path));  // 현재 경로 저장
        return;
    }

    for (int choice : getChoices(path)) {  // 가능한 모든 선택
		    if (!isValid(choice)) // 가지치기
		        continue;

        path.add(choice);  // 현재 선택 추가
        backtrack(path);   // 다음 단계 탐색
        path.remove(path.size() - 1);  // 원래 상태로 되돌리기 (Backtracking)
    }
}

---

💻 연습 문제

1️⃣ climbing stairs

import java.util.*;

class Solution {
    Map<Integer, Integer> fibo = new HashMap<>();
    public int climbStairs(int n) {
        if( n == 1 || n == 2 ){
            return n;
        }

        if(!fibo.containsKey(n)) {
            fibo.put(n, climbStairs(n-2) + climbStairs(n-1));
        }
        return fibo.get(n);
    }
}

 

2️⃣ min cost climbing stairs

import java.util.*;
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] minCost = new int[cost.length];
        Arrays.fill(minCost, Integer.MAX_VALUE);
        minCost[0] = cost[0];
        minCost[1] = cost[1];
        
        if(cost.length == 2) {
            return Math.min(cost[0], cost[1]);
        }

        for(int i = 2; i < cost.length; i++) {
            minCost[i] = cost[i] + Math.min(minCost[i-1], minCost[i-2]);
        }

        return Math.min(minCost[cost.length-1], minCost[cost.length-2]);
    }
}

 

3️⃣ House Robber

import java.util.*;
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }

        int[] money = new int[nums.length];
        
        money[0] = nums[0];
        money[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++) {
            money[i] = Math.max(money[i-2] + nums[i], money[i-1]);
        }

        return money[nums.length-1];
    }
}

 

4️⃣ Unique paths

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n ==1) 
            return 1;

        int N = Math.max(m, n)-1;
        int M = Math.min(m, n)-1;
        
        long ans = 1;

        for(int i = 0; i < M; i++) {
            ans = ans * (N+M-i) / (i+1);
        }
        
        return (int) ans;
    }
}

 

5️⃣ Longest Increasing Subsequence

import java.util.*;
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i = 0 ; i < nums.length; i++) {
            for(int j = 0 ; j < i ; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        Arrays.sort(dp);
        return dp[nums.length-1];
    }
}

 

6️⃣ Longest Common Subsequence

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        
        for(int i = 0 ; i <= n ; i++) {
            dp[i][0] = 0;
        }

        for(int j = 0 ; j <= m ; j++) {
            dp[0][j] = 0;
        }

        char[] charArr1 = text1.toCharArray();
        char[] charArr2 = text2.toCharArray();

        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= m ; j++) {
                if(charArr1[i-1] == charArr2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

 

7️⃣ Maximal Square

class Solution {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        int[][] dp = new int[row][col];

        int ans = 0; 

        for(int i = 0 ; i < row ; i++) {
            dp[i][0] = matrix[i][0]-'0';
            ans = Math.max(ans, dp[i][0]);
        }

        for(int j = 0 ; j < col ; j++) {
            dp[0][j] = matrix[0][j]-'0';
            ans = Math.max(ans, dp[0][j]);
        }

        if(row == 1 || col == 1) {
            return ans;
        }

        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j ++) {
                if(matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans*ans;
    }
}