组合 | LeetCode-77 | 回溯算法 |

回溯算法练习题

题目1：77.组合

1.题目描述

给定两个整数 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]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

2.题解

2.1 回溯算法

class Solution {
    // 结果列表，用于存储所有组合
    List<List<Integer>> result = new ArrayList<>();
    // 当前路径，用于生成组合
    List<Integer> path = new ArrayList<>();

    // 主函数，生成1到n中选择k个数字的所有组合
    public List<List<Integer>> combine(int n, int k) {
        // 开始回溯，从数字1开始
        backtracking(n, k, 1);
        // 返回所有组合的结果
        return result;
    }

    // 回溯函数，n是范围的上限，k是组合的大小，startIndex是当前数字的起始索引
    public void backtracking(int n, int k, int startIndex) {
        // 如果当前路径的大小等于k，说明已经生成了一个合法的组合
        if (path.size() == k) {
            // 将当前路径的拷贝添加到结果列表中
            result.add(new ArrayList<>(path));
            // 退出当前回溯
            return;
        }

        // 从startIndex开始，遍历到n
        for (int i = startIndex; i <= n; i++) {
            // 将当前数字添加到路径中
            path.add(i);
            // 递归调用回溯函数，继续生成组合
            backtracking(n, k, i + 1);
            // 回溯，将最后一个数字从路径中移除
            path.remove(path.size() - 1);
        }
    }
}

• 注意细节：
  • 细节1：每次递归的开始索引都是i+1，这样保证了不会重复，例如出现[3,4]和[4,3]的现象
  • 细节2：

2.2 回溯优化

• 图解：

• 代码：

class Solution {
    // 结果列表，用于存储所有组合
    List<List<Integer>> result = new ArrayList<>();
    // 当前路径，用于生成组合
    List<Integer> path = new ArrayList<>();

    // 主函数，生成1到n中选择k个数字的所有组合
    public List<List<Integer>> combine(int n, int k) {
        // 开始回溯，从数字1开始
        backtracking(n, k, 1);
        // 返回所有组合的结果
        return result;
    }

    // 回溯函数，n是范围的上限，k是组合的大小，startIndex是当前数字的起始索引
    public void backtracking(int n, int k, int startIndex) {
        // 如果当前路径的大小等于k，说明已经生成了一个合法的组合
        if (path.size() == k) {
            // 将当前路径的拷贝添加到结果列表中
            result.add(new ArrayList<>(path));
            // 退出当前回溯
            return;
        }

        // 优化：计算当前可以选择的数字的最大值
        // 减少无效递归的次数，确保路径中还可以添加足够的数字以满足组合的长度要求
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            // 将当前数字添加到路径中
            path.add(i);
            // 递归调用回溯函数，继续生成组合
            backtracking(n, k, i + 1);
            // 回溯，将最后一个数字从路径中移除
            path.remove(path.size() - 1);
        }
    }
}

• 代码说明：
  • 已经选择的元素个数：path.size();
  • 还需要的元素个数为: k - path.size();
  • 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

题目2：39.组合总和

1.题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

2.题解

class Solution {
    // 存储所有符合条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 用于存储当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法，用于调用回溯算法并返回结果
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 从第一个元素开始进行回溯
        backtracking(candidates, target, 0, 0);
        return result; // 返回所有符合条件的组合结果
    }

    // 回溯方法，用于寻找所有和为 target 的组合
    public void backtracking(int[] candidates, int target, int sum, int start) { 
        // 如果当前路径的和等于目标值，将当前路径加入结果列表
        if (sum == target) {
            result.add(new ArrayList<>(path)); // 将当前路径的副本加入结果集
            return; // 回溯终止，返回上层调用
        }

        // 遍历候选数组，寻找下一步可能的组合
        for (int i = start; i < candidates.length && sum < target; i++) {
            path.add(candidates[i]); // 将当前元素加入路径
            // 递归调用回溯方法，继续寻找下一步组合
            backtracking(candidates, target, sum + candidates[i], i); 
            path.remove(path.size() - 1); // 回溯，移除最后一个加入的元素
        }
    }
}

题目3：40.组合总和II

1.题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

2.题解

写法1

题目4：216.组合总和III

1.题目描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

2.题解

2.1 写法1

class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 从数字1开始进行回溯
        backtracking(k, n, 1);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            int sum = 0;
            // 计算路径中所有数字的总和
            for (int i = 0; i < k; i++) sum += path.get(i);
            // 如果总和等于目标值n，则将该路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 从startIndex开始遍历数字1到9
        for (int i = startIndex; i <= 9; i++) {
            path.add(i); // 将当前数字加入路径
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
        }
    }
}

2.2 优化1

class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 从数字1开始进行回溯
        backtracking(k, n, 1);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            int sum = 0;
            // 计算路径中所有数字的总和
            for (int i = 0; i < k; i++) sum += path.get(i);
            // 如果总和等于目标值n，则将该路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 优化后的循环：限制循环范围以减少不必要的遍历
        // 当path.size()已选择的数字数和剩余的k-path.size()个数字无法满足1-9的范围时，循环提前结束
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i); // 将当前数字加入路径
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
        }
    }
}

2.3 优化2（推荐）

class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 初始化回溯，起始索引为1，总和为0
        backtracking(k, n, 1, 0);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex, int sum) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            // 如果当前路径的总和等于目标值n，则将路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 优化后的循环：限制循环范围以减少不必要的遍历
        // 当剩余的数字数量不足以组成所需的k个数字时，提前结束循环
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i); // 将当前数字加入路径
            //sum += i; // 更新当前路径的总和
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1, sum + i);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
            //sum -= i; // 恢复总和为添加当前数字之前的值
        }
    }
}