Leetcode 216.组合总和III

力扣传送门(opens new window)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路：

做过Leetcode 77.组合再来做这道题会变得很简单。只不过这道题增加了一个条件相加之和为 n，那么我们来看下这道题目，还是使用回溯算法来进行求解。

确定递归函数参数

和Leetcode 77.组合一样，依然需要一个容器来存放符合条件的结果，这里依然使用stack栈，二维数组res来存放结果集。

这里我依然定义 res 为全局变量。

接下来还需要如下参数：

• n（int）目标和
• k（int）就是题目中要求k个数的集合。
• sum（int）为已经收集的元素的总和，也就是stack里元素的总和。
• begin（int）为下一层for循环搜索的起始位置。

确定终止条件

在上面已经说了，k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。

所以如果stack.size() 和 k相等了，就终止。

如果此时stack里收集到的元素和（sum） 和 n 相同了，就用res 收集当前的结果。

具体的步骤如下：

1. 创建一个成员变量 res，用于存储最终的结果列表。
2. 创建一个 Stack 类型的栈对象 stack，用于存储当前正在构建的组合。
3. 调用 backtracking 方法，传入参数 k、n、1（起始数字）、stack 和 0（当前和的初始值）。
4. backtracking 方法是回溯算法的具体实现。它接收五个参数：k（需要找到的组合的个数）、n（目标和）、begin（当前数字的起始值）、stack（当前正在构建的组合）、sum（当前和）。
5. 首先进行终止条件的判断。如果当前和 sum 大于目标和 n，说明当前组合不符合条件，直接返回。如果栈的大小等于 k 并且当前和等于目标和，说明找到了一个符合条件的组合，将其添加到结果列表 res 中，并返回。
6. 在 backtracking 方法中使用一个循环，从 begin 到 9 的范围内选择一个数字 i。
7. 将数字 i 压入栈 stack 中，表示选择了该数字。
8. 更新当前和 sum，将其加上 i。
9. 递归调用 backtracking 方法，传入更新后的参数：k、n、i+1（下一个数字的起始值）、stack 和 sum。
10. 在递归调用返回后，表示已经处理完了当前选择的数字 i，需要将其从栈 stack 中弹出，以便尝试其他的选择。
11. 同样，更新当前和 sum，将其减去 i。
12. 当所有的循环都结束后，方法 backtracking 执行完毕。
13. 返回结果列表 res。

代码实现：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {

    List<List<Integer>> res = new ArrayList(); // 存储结果的列表

    public List<List<Integer>> combinationSum3(int k, int n) {
        // 如果 k 或 n 小于等于 0，则返回空结果列表
        if(k <= 0 || n <= 0){ 
            return res;
        }
        Stack<Integer> stack = new Stack(); // 使用栈来辅助回溯
        backtracking(k, n, 1, stack, 0); // 调用回溯函数进行求解
        return res; // 返回最终结果列表
    }

    /**
     * 回溯函数
     * @param k 组合中元素的个数
     * @param n 目标和
     * @param begin 当前可选的起始数字
     * @param stack 当前的组合栈
     * @param sum 当前组合的和
     */
    public void backtracking(int k, int n, int begin, Stack stack, int sum) {
        // 如果当前组合的和大于目标和，则返回
        if (sum > n) { 
            return; 
        }
        // 如果当前组合的元素个数等于 k 并且和等于 n，则将组合加入结果列表
        if (stack.size() == k && sum == n) { 
            res.add(new ArrayList(stack));
            return;
        }
        // 遍历可选的数字
        for (int i = begin; i <= 9; i++) { 
        // 将数字加入组合栈
            stack.push(i); 
            sum += i; // 更新当前组合的和
            backtracking(k, n, i + 1, stack, sum); // 递归调用回溯函数，继续构建组合
            stack.pop(); // 回溯，将数字从组合栈中弹出
            sum -= i; // 回溯，更新当前组合的和
        }
    }
}