LeetCode、216. 组合总和 III【中等，组合型枚举】

news/2024/12/23 2:30:15/

文章目录

前言
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(mⁿ!)，空间复杂度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;}}}