Day27~77. 组合

开发运维 2023-10-02 大白菜程序猿 手机阅读

摘要

本文主要介绍了回溯算法的理论基础和回溯法模版，以及LeetCode中77.组合问题的解题思路和代码。

1、回溯算法理论基础

1.1 概念

回溯算法是一种用于解决组合问题、排列问题和搜索问题的常用算法。它基于深度优先搜索的思想，通过不断地尝试各种可能的选择，然后回退到上一步，直到找到问题的解或穷尽所有可能性。

回溯算法的核心思想是构建一棵决策树，每个节点表示在问题中的一个决策点，从根节点出发，逐步向下扩展树，直到找到解或无法继续扩展。如果遇到无法继续扩展的情况，就回退到上一层节点，尝试其他分支。

以下是回溯算法的基本框架和关键要点：

  • 路径（Path）： 在算法执行过程中，需要维护一个路径，用于记录当前的选择或决策。
  • 选择列表（Choices）： 每一步都有一个或多个选择，算法需要生成当前状态下的所有候选选择。
  • 结束条件（Termination Condition）： 定义何时达到问题的解，当满足结束条件时，算法结束。
  • 回溯过程（Backtracking）： 如果当前路径无法达到解或满足条件，算法需要回退到上一个状态，尝试其他选择。

    • 下面是一个简单的 Java 示例，用于解决组合问题（找到数组中所有可能的组合）：

    import java.util.ArrayList;
import java.util.List;
​
public class BacktrackingExample {
    public List combine(int n, int k) {
        List result = new ArrayList();
        List path = new ArrayList();
        backtrack(result, path, n, k, 1);
        return result;
    }
​
    private void backtrack(List result, List path, int n, int k, int start) {
        // 结束条件：已选择的元素数量达到 k
        if (path.size() == k) {
            result.add(new ArrayList(path));
            return;
        }
​
        // 选择列表：从 start 到 n 中选择一个数加入当前组合
        for (int i = start; i  n 时，表示已经考虑完了所有可选数字，直接返回。