当前位置：首页 > article >正文

【回溯】力扣 77.组合

article 2024/11/1 12:45:47

一、题目

在这里插入图片描述

二、思路

采用回溯算法，注意点：

递归出口：已经选够 $k$ 个数
参数传递：由于不可以重复选择相同的数字，因此每选一个数就会使得可选择的范围对应缩小。不妨设定选择的顺序是从 $1$ 到 $n$ 依次进行选择，那么假如当前选择的是 $i$ （ $\leq i \leq n$ ）那么下次进行选择只可以从 $i + 1$ 到 $n$ 进行选择，所以在写递归函数时需要，传递进行开始选择的位置（例如此例中需要传递 $i + 1$ ）。
剪枝优化：我们的目标是选够 $k$ 个数，回溯算法其实就是在暴力搜索，每次都走到尽头才进行“归”，在很多时候会进行不必要的搜索，例如当剩余可选的个数已经不足还需选择的个数时，回溯算法还在进行搜索。此时，就可以进行剪枝操作进行优化。检查当前可以选择的个数是否大于等于剩余可选择个数，可列出以下式子： $\leq n - i + 1$ ，根据此式得出 $\leq n －(k - path.size()) ＋ 1$

三、代码

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