Backtracking

1. N-Queens 문제

• N-Queens 문제는 N x N 체스판에 N개의 퀸을 서로 공격하지 못하도록 배치하는 문제입니다.

void solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');  // 체스판 초기화
    }
    List<List<String>> solutions = new ArrayList<>();
    backtrack(board, 0, solutions);
}

void backtrack(char[][] board, int row, List<List<String>> solutions) {
    if (row == board.length) {
        solutions.add(construct(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';  // 퀸 배치
            backtrack(board, row + 1, solutions);  // 다음 행으로 이동
            board[row][col] = '.';  // 백트래킹
        }
    }
}

boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;  // 같은 열에 퀸이 있는지 확인
    }

    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;  // 왼쪽 대각선에 퀸이 있는지 확인
    }

    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;  // 오른쪽 대각선에 퀸이 있는지 확인
    }

    return true;
}

List<String> construct(char[][] board) {
    List<String> solution = new ArrayList<>();
    for (int i = 0; i < board.length; i++) {
        solution.add(new String(board[i]));
    }
    return solution;
}

---

2. Subsets 문제

• 모든 부분 집합 구하기 (백트래킹을 사용한 조합):

void subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsets(result, new ArrayList<>(), nums, 0);
}

void backtrackSubsets(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
    result.add(new ArrayList<>(tempList));

    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]);  // 요소 추가
        backtrackSubsets(result, tempList, nums, i + 1);  // 다음 단계로 진행
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

3. Combination Sum 문제

• 주어진 배열에서 가능한 모든 조합으로 합이 target이 되는 조합 찾기:

void combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombinationSum(result, new ArrayList<>(), candidates, target, 0);
}

void backtrackCombinationSum(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
    if (remain < 0) return;  // 조건을 만족하지 않으면 종료
    if (remain == 0) result.add(new ArrayList<>(tempList));  // 합이 target이 되면 결과에 추가

    for (int i = start; i < candidates.length; i++) {
        tempList.add(candidates[i]);  // 요소 추가
        backtrackCombinationSum(result, tempList, candidates, remain - candidates[i], i);  // 재귀 호출
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

4. Permutations 문제

• 주어진 배열의 모든 순열을 구하는 문제:

void permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPermutations(result, new ArrayList<>(), nums);
}

void backtrackPermutations(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
    if (tempList.size() == nums.length) {
        result.add(new ArrayList<>(tempList));  // 모든 요소를 다 사용한 경우 결과에 추가
    } else {
        for (int i = 0; i < nums.length; i++) {
            if (tempList.contains(nums[i])) continue;  // 이미 사용한 숫자는 건너뜀
            tempList.add(nums[i]);  // 요소 추가
            backtrackPermutations(result, tempList, nums);  // 재귀 호출
            tempList.remove(tempList.size() - 1);  // 백트래킹
        }
    }
}

---

5. Palindrome Partitioning 문제

• 주어진 문자열을 가능한 모든 팰린드롬 부분 문자열로 나누기:

void partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrackPalindrome(result, new ArrayList<>(), s, 0);
}

void backtrackPalindrome(List<List<String>> result, List<String> tempList, String s, int start) {
    if (start == s.length()) {
        result.add(new ArrayList<>(tempList));  // 끝까지 탐색 완료된 경우 결과에 추가
    } else {
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                tempList.add(s.substring(start, i + 1));  // 팰린드롬인 경우 추가
                backtrackPalindrome(result, tempList, s, i + 1);  // 재귀 호출
                tempList.remove(tempList.size() - 1);  // 백트래킹
            }
        }
    }
}

boolean isPalindrome(String s, int low, int high) {
    while (low < high) {
        if (s.charAt(low++) != s.charAt(high--)) return false;
    }
    return true;
}

---

6. Word Search 문제

• 2D 그리드에서 주어진 단어를 찾는 문제 (백트래킹 사용):

boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (backtrackWordSearch(board, word, i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

boolean backtrackWordSearch(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;  // 모든 문자 탐색 완료
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
        return false;  // 조건에 맞지 않으면 종료
    }

    char temp = board[i][j];
    board[i][j] = '*';  // 이미 방문한 곳은 '*'로 표시

    boolean found = backtrackWordSearch(board, word, i + 1, j, index + 1)
            || backtrackWordSearch(board, word, i - 1, j, index + 1)
            || backtrackWordSearch(board, word, i, j + 1, index + 1)
            || backtrackWordSearch(board, word, i, j - 1, index + 1);

    board[i][j] = temp;  // 백트래킹 후 복원
    return found;
}