【代码随想录】回溯算法刷题

视频：带你学透回溯算法（理论篇）
参考文档：代码随想录 (programmercarl.com)

回溯法，一般可以解决如下几种问题：

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

组合无序，排列有序

回溯算法模板框架：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合

题目：77. 组合 - 力扣（LeetCode）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int n, k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        dfs(new ArrayList<>(), 1);
        return res;
    }

    void dfs(List<Integer> path, int begin) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i <= n; i++) {
            path.add(i);
            dfs(path, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

组合总和 III

题目：216. 组合总和 III - 力扣（LeetCode）

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字 1 到 9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int k, n;

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.k = k;
        this.n = n;
        dfs(new ArrayList<>(), 0, 1); 
        return res;
    }

    void dfs(List<Integer> path, int sum, int u) {
        if (sum > n) return; // 剪枝
        if (sum == n && path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = u; i <= 9; i++) {
            sum += i;
            path.add(i);
            dfs(path, sum, i + 1); 
            sum -= i;
            path.remove(path.size() - 1);
        }
    }
}

电话号码的字母组合

题目：17. 电话号码的字母组合 - 力扣（LeetCode）

标准回溯模板 + StringBuilder：

class Solution {
    Map<Integer, String> map = Map.of(
            2, "abc", 3, "def", 4, "ghi", 5, "jkl",
            6, "mno", 7, "pqrs", 8, "tuv", 9, "wxyz");
    List<String> res = new ArrayList<>();
    String digits;

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return res;
        this.digits = digits;
        dfs(new StringBuilder(), 0);
        return res;
    }

    void dfs(StringBuilder path, int idx) {
        if (idx == digits.length()) {
            res.add(path.toString());
            return;
        }
        String letters = map.get(digits.charAt(idx) - '0');
        for (int i = 0; i < letters.length(); i++) {
            path.append(letters.charAt(i));
            dfs(path, idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

组合总和 I

题目：39. 组合总和 - 力扣（LeetCode）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int [] candidates;
    int target;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        Arrays.sort(this.candidates); // 剪枝的前提
        dfs(new ArrayList<>(), 0, 0);
        return res;
    }

    void dfs(List<Integer> path, int sum, int start) {
        // if (sum > target) return;
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 下一层的 sum 会大于 target，则不用进行后续递归
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            path.add(candidates[i]);
            dfs(path, sum, i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

组合总和 II

题目：40. 组合总和 II - 力扣（LeetCode）

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] candidates;
    int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;
        dfs(new ArrayList<>(), 0, 0);
        return res;
    }

    void dfs(List<Integer> path, int sum, int start) {
        if (sum > target) return;
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 去重
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            path.add(candidates[i]);
            dfs(path, sum, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1); 
        }
    }
}

分隔回文串

题目：131. 分割回文串 - 力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, new ArrayList<>(), 0);
        return res;
    }

    void dfs(String s, List<String> path, int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String ss = s.substring(start, i + 1); // 切割 
            if (isPalindrome(ss)) {
                path.add(ss);
                dfs(s, path, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断是否是回文串
    boolean isPalindrome(String s) {
        return s.equals(new StringBuilder(s).reverse().toString());
    }
}

复原 IP 地址

题目：93. 复原 IP 地址 - 力扣（LeetCode）

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

输入：s = "0000"
输出：["0.0.0.0"]

class Solution {
    List<String> res = new ArrayList<>();
    String s;

    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        dfs("", 0, 0);
        return res;
    }

    void dfs(String path, int start, int cnt) {
        // 根据 IP 地址长度进行剪枝
        if (12 - cnt * 3 < s.length() - path.length()) return;
        if (cnt == 4 && path.length() >= s.length() + 4) {
            res.add(path.substring(0, path.length() - 1)); // 去除最后的 .
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String ss = s.substring(start, i + 1);
            if (ss.equals("0") || !ss.startsWith("0") && ss.length() <= 3 && Integer.parseInt(ss) <= 255) {
                path += ss + ".";
                dfs(path, i + 1, cnt + 1);
                path = path.substring(0, path.length() - ss.length() - 1);
            }
        }
    }
}

回溯部分的其他写法：

for (int i = start; i < s.length(); i++) {
	String ss = s.substring(start, i + 1);
	if (ss.equals("0") || !ss.startsWith("0") && ss.length() <= 3 && Integer.parseInt(ss) <= 255) {
		dfs(path + ss + ".", i + 1, cnt + 1);
	}
}

子集 I

题目：78. 子集 - 力扣（LeetCode）

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

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(new ArrayList<>(), 0);
        return res;
    }

    void dfs(List<Integer> path, int start) {
        res.add(new ArrayList<>(path)); // 每次都将结果添加进来

        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(path, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

子集 II

题目：90. 子集 II - 力扣（LeetCode）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 检查元素重复的前提
        this.nums = nums;
        dfs(new ArrayList<>(), 0);
        return res;
    }

    void dfs(List<Integer> path, int start) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            // 不添加重复元素
            if (i != start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            dfs(path, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

递增子序列

题目：491. 递增子序列 - 力扣（LeetCode）

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> findSubsequences(int[] nums) {
        this.nums = nums;
        dfs(new ArrayList<>(), 0);
        return res;
    }

    void dfs(List<Integer> path, int start) {
        if (path.size() >= 2) res.add(new ArrayList<>(path));
        // 每层的新建一个哈希表用于去重
        boolean[] used = new boolean[201]; // 标记已经使用过
        for (int i = start; i < nums.length; i++) {
            // 必须满足递增的条件
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)
                    || used[nums[i] + 100]) continue;
            used[nums[i] + 100] = true; // 标记已经使用
            path.add(nums[i]);
            dfs(path, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

全排列 I

题目：46. 全排列 - 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入：nums = [1,2,3]
输出：
[[1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]]

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums; 

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        dfs(new ArrayList<>(), new boolean[nums.length], 0);
        return res;
    }

    void dfs(List<Integer> path, boolean[] used, int u) {
        if (u == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            dfs(path, used, u + 1);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

全排列 II

题目：47. 全排列 II - 力扣（LeetCode）

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

方法一：使用 nums[i] == nums[i - 1] 去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        Arrays.sort(nums);
        dfs(new ArrayList<>(), new boolean[nums.length], 0);
        return res;
    }

    void dfs(List<Integer> path, boolean[] used, int start) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) continue;

            if (used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            dfs(path, used, i + 1);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

方法二：使用 tmpUsed 数组进行去重

// 使用 tmpUsed 数组去重
class Solution2 {
    List<List<Integer>> res = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.nums = nums;
        dfs(new ArrayList<>(), new boolean[nums.length], 0);
        return res;
    }

    void dfs(List<Integer> path, boolean[] used, int start) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        boolean[] tmpUsed = new boolean[21];
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || tmpUsed[nums[i] + 10]) continue;
            path.add(nums[i]);
            used[i] = true;
            tmpUsed[nums[i] + 10] = true;
            dfs(path, used, i + 1);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

重新安排行程 - hard

题目：332. 重新安排行程 - 力扣（LeetCode）

class Solution {
    List<String> res = new ArrayList<>();
    Map<String, PriorityQueue<String>> map = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src))
                map.put(src, new PriorityQueue<>());
            map.get(src).add(dst);
        }
        // 查看存储的数据
        // map.forEach((k, v) -> {
        //     System.out.print("k = " + k + "  ");
        //     v.forEach(e -> System.out.print(" v = " + e + " "));
        //     System.out.println();
        // });
        dfs("JFK");
        return res;
    }

    void dfs(String src) {
        PriorityQueue<String> pq = map.get(src);
        while (pq != null && !pq.isEmpty())
            dfs(pq.poll());
        res.add(0, src);
    }
}

N 皇后 - hard

题目：51. N 皇后 - 力扣（LeetCode）

class Solution {
    final int N = 20;
    List<List<String>> res = new ArrayList<>();
    char[][] g = new char[N][N];
    boolean[] col = new boolean[N]; // 某一行是否被访问过
    boolean[] dg = new boolean[N]; // 对角是否被访问过
    boolean[] udg = new boolean[N]; // 反对角是否被访问过
    int n;

    public List<List<String>> solveNQueens(int n) {
		// 初始化为 .
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = '.';
        this.n = n;
        dfs(0); // 从第 0 行开始
        return res;
    }

    // 当前遍历的行
    void dfs(int u) {
        if (u == n) {
            List<String> tmpList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++)
                    sb.append(g[i][j]);
                tmpList.add(sb.toString());
            }
            res.add(tmpList);
        }
        int x = u;
        for (int y = 0; y < n; y++) {
            if (col[y] || dg[y - x + n] || udg[y + x]) continue;
            col[y] = dg[y - x + n] = udg[y + x] = true;
            g[x][y] = 'Q';
            dfs(x + 1);
            col[y] = dg[y - x + n] = udg[y + x] = false;
            g[x][y] = '.';
        }
    }
}

解数独 - hard

题目：37. 解数独 - 力扣（LeetCode）

class Solution {
    public void solveSudoku(char[][] board) {
        dfs(board);
    }

    boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                // 尝试 1~9 的数字
                for (char n = '1'; n <= '9'; n++) {
                    if (check(board, i, j, n)) {
                        board[i][j] = n; // 填入数字
                        // 找到解直接返回
                        if (dfs(board)) return true;
                        board[i][j] = '.'; // 回溯
                    }
                }
                return false; // 9 个数字都试完了
            }
        }
        return true; // 正常遍历完就是找到解
    }

    // 在 board[x][y] 位置放置 k 是否合法
    boolean check(char[][] board, int x, int y, int k) {
        // 检查 当前列 和 当前行 是否合法
        for (int i = 0; i < 9; i++) 
            if (board[i][y] == k || board[x][i] == k)
                return false;
        // 检查当前 3x3 宫内是否合法，定位到 3x3 宫位置
        // (xx, yy) 3x3 宫左上角, (xx + 2, yy + 2) 3x3 宫右下角
        int xx = x / 3 * 3, yy = y / 3 * 3;
        for (int i = xx; i <= xx + 2; i++) 
            for (int j = yy; j <= yy + 2; j++) 
                if (board[i][j] == k) return false;
        return true;
    }
}