【LeetCode:216. 组合总和 III + 递归】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ 递归
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 💬 共勉

🚩 题目链接

216. 组合总和 III

⛲ 题目描述

找出所有相加之和为 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

🌟 求解思路&实现代码&运行结果

⚡ 递归

🥦 求解思路

该题目通过递归来求解，在1到9的数字中，找到k个可以组成n的不同结果的形式返回。注意，数组中的元素最多可以选择一次。
有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, k, n);
        return ans;
    }

    public void dfs(int index, int k, int n) {
        if (index > 10 || k < 0 || n < 0) {
            return;
        }
        if (k == 0 && n == 0) {
            ans.add(new ArrayList<>(list));
        }
        for (int i = index; i < 10; i++) {
            list.add(i);
            dfs(i + 1, k - 1, n - i);
            list.remove(list.size() - 1);
        }
    }
}