回溯算法相关题目

回溯算法是一种基于递归的暴力搜索算法。它适用于排列、组合、切割、子集和棋盘类型的问题。

public void backTracking([[prameter list]]) {
    if ([[ternimate condition]]) {
        // result collection
    }

    for (ele : collection of current level) {
        // elements process
        // recursion
        // back tracking
    }
}

组合

组合 LeetCode 77

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

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

示例 1
输入：n = 4, k = 2
输出：

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2
输入：n = 1, k = 1
输出：[[1]]

解法

class Solution {
    List result = new ArrayList();
    List path = new ArrayList();

    // 数字集合 1-n, 取 k 个数进行组合, 每次判断的起始位是 startIndex
    public void backTracking(int n, int k, int startIndex) {
        // 终止条件
        if (path.size() == k) {                 // 树的深度就是要取的组合位数
            result.add(new ArrayList(path));    // 把当前路径作为其中一个结果放进结果集
            return;
        }

        // 横向处理本层
        for (int i = startIndex; i <= n; i++) { // 从 startIndex 到结尾，每个都取一次生成新树
            // 处理结点
            path.add(i);                    // 取当前数字作为一个路径加入 path
            // 递归
            backTracking(n, k, i + 1);      // 从下一个数字开始作为下一层重复
            // 回溯撤回
            path.remove(path.size() - 1);   // 回溯，去掉当前数字，处理本层第二个元素
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }
}

改进
[分析]
当在横向处理时，剩余元素个数不足以组合成 k 个数字时，则可以提前停下。即生成新树有前提条件，元素个数不满足的可以不用考虑。所以可以对循环条件修改来减少遍历元素个数。
所有元素数量： n 当前处理过的元素数量： path.size()
单个结果需要总元素： k
单个结果需要的剩余元素数量： k - path.size() 符合条件的最后的需要遍历开始位置： n - (k - path.size()) + 1

例如 n = 5, k = 3 时。如果当前还没有遍历元素，则：5 - (3 - 0) + 1 = 3.
即从 3 开始遍历是最后一个可以被接受的组合，如 [3 4 5]，而 4 开头和 5 开头都因为个数不够而剪枝。
剪枝操作在当前选择个数小时最有效，当已选择的个数多时，结果一般都会为完全遍历。

class Solution {
    List result = new ArrayList();
    List path = new ArrayList();

    // 数字集合 1-n, 取 k 个数进行组合, 每次判断的起始位是 startIndex
    public void backTracking(int n, int k, int startIndex) {
        // 终止条件
        if (path.size() == k) {                 // 树的深度就是要取的组合位数
            result.add(new ArrayList(path));    // 把当前路径作为其中一个结果放进结果集
            return;
        }

        // 横向处理本层
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 从 startIndex 到合适的结尾，每个都取一次
            // 处理结点
            path.add(i);                    // 取当前数字作为一个路径加入 path
            // 递归
            backTracking(n, k, i + 1);      // 从下一个数字开始作为下一层重复
            // 回溯撤回
            path.remove(path.size() - 1);   // 回溯，去掉当前数字，处理本层第二个元素
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }
}