LeetCode、216. 组合总和 III【中等，组合型枚举】
文章目录
- 前言
- LeetCode、216. 组合总和 III【中等，组合型枚举】
- 题目类型与分类
- 思路
- 资料获取
前言
博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引：博客目录索引(持续更新)
视频平台：b站-Coder长路
LeetCode、216. 组合总和 III【中等，组合型枚举】
题目类型与分类
题目链接：LeetCode、216. 组合总和 III
题目类型：搜索与图论/回溯、基础算法/枚举（组合型枚举，n个数中取m个）
思路
思路描述：组合型枚举+选中的符合条件的情况案例
组合型模板直接套上，然后对选中的几个位置（state数组元素不为0的）求下和看是否是目标值，若是的话将这条情况添加到结果集中。
中间过程对于在1-9中是否选中，我们根据一个state数组来进行表示。
复杂度分析：时间复杂度O(mn!)，空间复杂度O(1)
import java.util.ArrayList;
import java.util.List;class Solution {public int n, m;public int[] state;//若为0表示没有选中，不为0表示选中public List<List<Integer>> res;//组合型枚举，n个数中取m个//本题为：1-9中取k个，和为npublic List<List<Integer>> combinationSum3(int k, int sum) {//表示从9个中选k个this.n = 9;this.m = k;this.state = new int[n];this.res = new ArrayList<>();dfs (0, 0, sum);return res;}/*** @param u 总计达到k个（取的k个数量）* @param start 当前应当开始的位置*/public void dfs (int u, int start, int sum) {//提前剪枝//u表示当前取了几个 n - start表示还有几个未取//若是两个相加不满足我们最终要取的个数，那么直接结束if (u + (n - start) < m) return;//若是刚好已经取到了m个if (u == m) {List<Integer> choice = new ArrayList<>();int s = 0;for (int i = 0; i < n; i++) {if (state[i] != 0) {s += state[i];choice.add(state[i]);}}if (s == sum) {res.add(choice);}}for (int i = start; i < n; i ++) {state[i] = i + 1;dfs (u + 1, i + 1, sum);state[i] = 0;}}}
资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅：在下方专栏👇🏻
- 长路-文章目录汇总（算法、后端Java、前端、运维技术导航）：博主所有博客导航索引汇总
- 开源项目Studio-Vue—校园工作室管理系统(含前后台，SpringBoot+Vue)：博主个人独立项目，包含详细部署上线视频，已开源
- 学习与生活-专栏：可以了解博主的学习历程
- 算法专栏：算法收录
更多博客与资料可查看👇🏻获取联系方式👇🏻，🍅文末获取开发资源及更多资源博客获取🍅
整理者：长路 时间：2024.1.31