LeetCode：77. 组合——回溯法，是暴力法？-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode：77. 组合——回溯法，是暴力法？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

一、🌱77. 组合

题目描述：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。
来源：力扣（LeetCode）
难度：中等
提示：
1 <= n <= 20
1 <= k <= n
示例 1：
输入：n = 4, k = 2
输出：
[[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4]]
示例 2：
输入：n = 1, k = 1
输出：[[1]]

🌴解题

输入：n = 4, k = 2
就是遍历这样的一个树，选取组合。
LeetCode：77. 组合——回溯法，是暴力法？

回溯code：

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans= new ArrayList<>();
        List<Integer> nk=new ArrayList<>();
        getnk(n,k,ans,nk,1);
        return ans;
    }
    private static void getnk(int n, int k,List<List<Integer>> ans, List<Integer> nk,int index) {
        if(nk.size()==k){
            ans.add(new ArrayList<>(nk));
            return;
        }
        for (int i = index; i <= n; i++) {
            nk.add(i);
            getnk(n,k,ans,nk,i+1);
            nk.remove((Object) i);
        }
    }
}

二、🌱回溯法：

回溯算法是一种基于 DFS 搜索的算法思想，回溯算法可枚举出所有可能的情况，并通过剪枝等优化技巧减少搜索时间，从而求出问题的解。

在回溯算法中，我们通常需要定义以下几个概念：

状态：问题或问题的解可以表示为不同状态的组合。例如，在 8 皇后问题中，状态是一个长度为 8 的数组，在数组中，每个元素存储一个整数，表示皇后的位置。因此，所有可能的状态组成了问题的解空间。
决策：对于一个给定的状态，我们可以通过一种操作，生成不同的下一个状态。例如，在 8 皇后问题中，决策是指从当前状态中选择一个位置，将下一个皇后放在该位置。
可行性条件：在生成新状态之后，需要检查该状态是否满足问题的要求。如果新状态不满足要求，则需要回溯到前一个状态，进行其他的决策。

回溯算法是通过枚举所有可能的情况，逐个考虑每个决策，生成新的可能状态，检验状态是否满足问题要求。如果满足要求，继续生成下一个状态，否则回溯到上一个状态，选择其他的决策进行尝试。由于需要考虑所有可能的情况，因此回溯算法,具有非常高的时间复杂度，因此，需要合理地设置搜索条件、剪枝等技巧，以提高回溯算法的效率。

回溯算法通常需要进行以下几个操作：