递归与回溯

递归的基本概念

递归是一种解决问题的方法，它通过将问题分解为更小的子问题来解决。在递归函数中，函数调用自身来处理这些子问题。递归函数包括两个关键部分：基本情况和递归情况。基本情况是指解决问题的最简单情况，递归情况则是将问题分解为更小的子问题。

回溯的基本概念

回溯是一种通过尝试所有可能的选择来解决问题的方法。在回溯算法中，我们逐步构建解决方案，如果遇到无法继续前进的情况，就回退到上一个选择点，并尝试其他选择。回溯通常与递归结合使用，因为回溯算法本质上是递归的。

递归与回溯的联系

递归和回溯在解决问题时经常结合在一起使用。递归用于分解问题和处理子问题，而回溯用于搜索解决方案的所有可能性。递归函数通常包含回溯的部分，因为在解决问题时，我们经常需要尝试多个选择，并在每个选择之后递归地处理剩余的问题空间。

例子

字符串的排列组合

1.代码

 /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
     * 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> permSet = new ArrayList<>();
        Set<String> sets = new HashSet<>();
        permutation("", str, sets, str.length());
        return new ArrayList<String>(sets);
    }


    private static void permutation(String perm, String word, Set sets, int length) {
        if (word.isEmpty()) {
            sets.add(perm);
        } else {

            for (int i = 0; i < word.length(); i++) {
                permutation(perm + word.charAt(i),
                        word.substring(0, i) + word.substring(i + 1, word.length()), sets, length);
            }
        }
    }

2.图解

字符串为“ab”的情况

字符串为"abc"的情况

生成所有的由n对括号组成的合法组合

1.代码

import java.util.ArrayList;
import java.util.List;

public class Tmp2 {

    public static void main(String[] args) {
        Tmp2 solution = new Tmp2();
        int nums = 3;
        ArrayList<String> permutations = solution.generateParenthesis(nums);
        permutations.forEach(System.out::println);
    }

    /**
     * 生成所有合法的括号组合。
     *
     * @param n 括号对数。
     * @return 所有合法的括号组合。
     */
    public ArrayList<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(n, 0, 0, new StringBuilder(), result);
        return new ArrayList<>(result);
    }

    /**
     * 回溯生成合法的括号组合。
     *
     * @param n           括号对数。
     * @param openCount   已放置的左括号数。
     * @param closeCount  已放置的右括号数。
     * @param combination 当前括号组合。
     * @param result      结果列表。
     */
    private void backtrack(int n, int openCount, int closeCount,
                           StringBuilder combination, List<String> result) {
        if (openCount == n && closeCount == n) {
            result.add(combination.toString());
            return;
        }
        if (openCount < n) {
            combination.append('(');
            //递归调用
            backtrack(n, openCount + 1, closeCount, combination, result);
            //回溯
            combination.deleteCharAt(combination.length() - 1);
        }
        if (closeCount < openCount) {
            combination.append(')');
            //递归调用
            backtrack(n, openCount, closeCount + 1, combination, result);
           //回溯
            combination.deleteCharAt(combination.length() - 1);
        }
    }
}

2.图解

N皇后

1.描述

皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

2.代码

public class NQueens {

    public static void main(String[] args) {
        NQueens solution = new NQueens();
        int n = 4;
        List<List<String>> result = solution.solveNQueens(n);
        for (List<String> board : result) {
            for (String row : board) {
                System.out.println(row);
            }
            System.out.println();
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtrack(board, 0, result);
        return result;
    }

    private void backtrack(char[][] board, int row, List<List<String>> result) {
        System.out.println(Arrays.deepToString(board));
        if (row == board.length) {
            result.add(constructBoard(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }

    private 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;
    }

    private List<String> constructBoard(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }

3.图解