回溯算法核心原理与 Java 实现详解

回溯算法详解

1. 回溯方法概述

回溯法（Backtracking）也称为回溯搜索法，是一种通过递归探索所有可能解的搜索方式。回溯是递归的副产品，只要有递归就会有回溯。

1.1 适用问题类型

回溯法通常用于解决以下问题：

• 组合问题：从 N 个数中按规则找出 k 个数的集合。
• 切割问题：字符串按规则有几种切割方式。
• 子集问题：N 个数的集合里有多少符合条件的子集。
• 排列问题：N 个数按规则全排列，有几种排列方式。
• 棋盘问题：如 N 皇后、解数独等。

注意：组合无序，排列有序。

1.2 核心思想

回溯法解决的问题都可以抽象为树形结构。集合的大小构成树的宽度，递归的深度构成树的深度。递归必须有终止条件，因此必然是一棵高度有限的树（N 叉树）。

1.2.1 通用模板

void backtracking(参数) {
    // 终止条件
    if (满足终止条件) {
        存放结果;
        return;
    }
    // 遍历本层集合中的元素
    for (选择 : 本层集合中元素) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果;
    }
}

2. 经典题目实战

2.1 全排列

题目描述：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

思路： 排列是有序的，元素在 [1,2] 和 [2,1] 中都要使用一次。处理排列问题不需要 startIndex，每层都是从 0 开始搜索。需要 used 数组记录 path 里已放置的元素。

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

public class Main {
    List<List<Integer>> ans;
    List<Integer> path;

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        ans = new ArrayList<>();
        path = new ArrayList<>();
        int[] used = new int[n];
        backtracking(nums, used);
        return ans;
    }

    private void backtracking(int[] nums, int[] used) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1) continue;
            path.add(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            used[i] = 0;
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        int[] nums = {1, 2, 3};
        List<List<Integer>> ans = main.permute(nums);
        System.out.println(ans);
    }
}

2.2 子集

题目描述：给你一个整数数组 nums，元素互不相同。返回该数组所有可能的子集（幂集）。

思路： 回溯，主要弄懂结束条件和子集合限制。每一个次递归要加入结果，没有 if 判断直接加。子集问题属于集合问题，每一次的子集合不从 0 开始，从 startIndex 开始。

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

public class Main {
    List<List<Integer>> ans;
    List<Integer> path;

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

    private void backtracking(int[] nums, int startIndex) {
        ans.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        int[] nums = {1, 2, 3};
        List<List<Integer>> ans = main.subsets(nums);
        System.out.println(ans);
    }
}

2.3 电话号码的字母组合

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

思路： 回溯，使用哈希表模拟映射，使用 StringBuilder 来组装。

import java.util.*;

public class Main {
    Map<Character, char[]> map = new HashMap<>() {{
        put('2', new char[]{'a', 'b', 'c'});
        put('3', new char[]{'d', 'e', 'f'});
        put('4', new char[]{'g', 'h', 'i'});
        put('5', new char[]{'j', 'k', 'l'});
        put('6', new char[]{'m', 'n', 'o'});
        put('7', new char[]{'p', 'q', 'r', 's'});
        put('8', new char[]{'t', 'u', 'v'});
        put('9', new char[]{'w', 'x', 'y', 'z'});
    }};
    List<String> ans;
    StringBuilder word;

    public List<String> letterCombinations(String digits) {
        ans = new ArrayList<>();
        word = new StringBuilder();
        if (digits.isEmpty()) return ans;
        backtracking(digits, 0);
        return ans;
    }

    private void backtracking(String digits, int index) {
        if (word.length() == digits.length()) {
            ans.add(word.toString());
            return;
        }
        char[] letters = map.get(digits.charAt(index));
        for (char c : letters) {
            word.append(c);
            backtracking(digits, index + 1);
            word.deleteCharAt(word.length() - 1);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        List<String> ans = main.letterCombinations("23");
        System.out.println(ans);
    }
}

2.4 组合总和

题目描述：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。

思路： 回溯，终止条件就是满足这个和。同一个数字可以无限重复使用，每一层的子集会逐渐缩减。

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

public class Main {
    List<List<Integer>> ans;
    List<Integer> path;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ans = new ArrayList<>();
        path = new ArrayList<>();
        backtracking(candidates, 0, target);
        return ans;
    }

    private void backtracking(int[] candidates, int startIndex, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            target -= candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, i, target); // 注意这里传入 i 而不是 i+1，因为可以重复使用
            target += candidates[i];
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        int[] candidates = {2, 3, 6, 7};
        List<List<Integer>> ans = main.combinationSum(candidates, 7);
        System.out.println(ans);
    }
}

2.5 括号生成

题目描述：数字 n 代表生成括号的对数，设计函数生成所有可能的并且有效的括号组合。

思路： DFS 回溯。关键点有两个：

1. 当左括号数量 left < n 时还可以放左括号。
2. 当右括号的数量 right < left 时可以放置右括号。

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

public class Main {
    List<String> ans;
    StringBuilder parentthesis;

    public List<String> generateParenthesis(int n) {
        ans = new ArrayList<>();
        parentthesis = new StringBuilder();
        backtracking(0, 0, n);
        return ans;
    }

    private void backtracking(int left, int right, int n) {
        if (parentthesis.length() == 2 * n) {
            ans.add(parentthesis.toString());
            return;
        }
        if (left < n) {
            parentthesis.append("(");
            backtracking(left + 1, right, n);
            parentthesis.deleteCharAt(parentthesis.length() - 1);
        }
        if (right < left) {
            parentthesis.append(")");
            backtracking(left, right + 1, n);
            parentthesis.deleteCharAt(parentthesis.length() - 1);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        List<String> ans = main.generateParenthesis(3);
        System.out.println(ans);
    }
}

2.6 单词搜索

题目描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true。

思路： DFS 回溯。满足条件就返回 true。需使用剪枝优化，避免超时。

public class Solution {
    int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, boolean[][] visited, int x, int y, int index) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y] || !(word.charAt(index) == board[x][y])) {
            return false;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (dfs(board, word, visited, nextx, nexty, index + 1)) {
                return true;
            }
        }
        visited[x][y] = false;
        return false;
    }
}

2.7 分割回文串

题目描述：将字符串 s 分割成一些子串，使每个子串都是回文串。

思路： 切割问题类似组合问题。递归用来纵向遍历，for 循环用来横向遍历。切割线切割到字符串的结尾位置，说明找到了一个切割方法。

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

public class Main {
    List<List<String>> ans;
    List<String> path;

    public List<List<String>> partition(String s) {
        ans = new ArrayList<>();
        path = new ArrayList<>();
        backtracking(s, 0);
        return ans;
    }

    private void backtracking(String s, int startIndex) {
        if (startIndex >= s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isHuiwen(s, startIndex, i)) {
                String subStr = s.substring(startIndex, i + 1);
                path.add(subStr);
                backtracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isHuiwen(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        Main main = new Main();
        List<List<String>> ans = main.partition("aab");
        System.out.println(ans);
    }
}

同类高频：复原 IP 地址

题目描述：给定一个只包含数字的字符串 s，返回所有可能的有效 IP 地址。

思路： 将字符串分 3 次分为 4 段。参数需要 startIndex 和分割次数计数 count。终止条件是 count == 3 且最后一个也是正确的。需要判断字符数字范围在 0~255，且无前导零。

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

public class Main {
    List<String> ans;

    public List<String> restoreIpAddresses(String s) {
        ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder(s);
        backtracking(sb, 0, 0);
        return ans;
    }

    private void backtracking(StringBuilder sb, int startIndex, int count) {
        if (count == 3) {
            if (isValid(sb.toString(), startIndex, sb.length() - 1)) {
                ans.add(sb.toString());
            }
            return;
        }
        for (int i = startIndex; i < sb.length(); i++) {
            if (isValid(sb.toString(), startIndex, i)) {
                sb.insert(i + 1, ".");
                backtracking(sb, i + 2, count + 1);
                sb.deleteCharAt(i + 1);
            } else {
                break;
            }
        }
    }

    private boolean isValid(String s, int left, int right) {
        if (left > right) return false;
        if (s.charAt(left) == '0' && left != right) return false;
        if (right - left + 1 > 3) return false;
        try {
            int num = Integer.parseInt(s.substring(left, right + 1));
            return num >= 0 && num <= 255;
        } catch (NumberFormatException e) {
            return false;
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        List<String> ans = main.restoreIpAddresses("25525511135");
        System.out.println(ans);
    }
}

2.8 N 皇后

题目描述：将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

思路： 约束条件：不能同行、不能同列、不能同斜线。按行进行放置，一行只能放一个。Java 中 String 不可变，最好使用字符再拼接。

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

public class Main {
    List<List<String>> ans;

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        ans = new ArrayList<>();
        backtracking(board, n, 0);
        return ans;
    }

    private void backtracking(char[][] board, int n, int row) {
        if (row >= n) {
            ans.add(charsToList(board, n));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(board, n, row, i)) {
                board[row][i] = 'Q';
                backtracking(board, n, row + 1);
                board[row][i] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int n, int row, int col) {
        // 1. 同行没有，每行放一个已经解决
        // 2. 同列没有
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 3. 45 度主对角线没有
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 4. 135 度副对角线没有
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private List<String> charsToList(char[][] board, int n) {
        List<String> res = new ArrayList<>();
        for (char[] chars : board) {
            res.add(String.copyValueOf(chars));
        }
        return res;
    }

    public static void main(String[] args) {
        Main main = new Main();
        List<List<String>> ans = main.solveNQueens(4);
        System.out.println(ans);
    }
}