管理培训班_建设企业网站官网企业_济南网站制作_seo常用的优化工具

一、题目

二、思路

77.组合的基础上，可选数字变为1到9，多了一个约束条件为已选数字总和为 n。

三、代码

代码如下（示例）：

class Solution {List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;// 已选数字的总和public List<List<Integer>> combinationSum3(int k, int n) {dfs(n, k, 1);return ans;}public void dfs(int n, int k, int i) {if (sum > n) {// 优化：如果 sum 已经超出 n 则不必继续进行搜索return;}if (path.size() == k) {// 首先判断选择的个数if (sum == n) {	// 再判断总和是否为 nans.add(new ArrayList<>(path));}return;}for (int j = i; j <= 9 - (k - path.size()) + 1; j++) {// 这里沿用了 77题的剪枝优化，直接将个数写为 9path.add(j);sum += j;dfs(n, k, j + 1);sum -= j;path.remove(path.size() - 1);}}
}