回溯法

怎样理解回溯

回溯算法本质上也是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜素所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。
回溯算法通常采用深度优先搜索来遍历解空间，之所以称之为回溯算法，是因为该算法在搜素解空间时会采用尝试与回退的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。此外，复杂的回溯问题通常包含一个或多个约束条件，约束条件常常用来剪枝。
理解了以上基本概念，接下来尝试将回溯算法的尝试、回退、剪枝的主体框架提炼出来，提升代码的通用性。在以下框架代码中，state 表示问题的当前状态，choices 表示当前状态下可以做出的选择。

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

回溯算法可以用于解决许多搜索问题、约束满足问题和组合优化问题。

组合

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

• 回溯法，递归往下搜索，递归终止条件是 path 中已经含有 k 个数字
• 回溯法基本框架，理解并记忆

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k);
        return ans;
    }
    private void dfs(int i, int k) {
        if (k == path.size()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j >= k - path.size(); j--) {
            path.add(j);
            dfs(j - 1, k);
            path.remove(path.size() - 1);
        }
    }
}

电话号码的字符组合

力扣题目链接
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。