算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 组合总和 III，我们先来看题面：https://leetcode-cn.com/problems/combination-sum-iii/Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
题意
找出所有相加之和为 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]]
解题
碰到这种题直接用DFS一波带走，结束递归的条件-成功:和为n且组合个数为k，失败:和大于n或者组合个数大于k。需要在每次找到组合后删除最后一个添加元素，才能结束这轮递归；每轮在递归结束必须把当前最后一个元素删除。因为所求为组合，且数字不能重复，所以设置变量start，从1开始往下走，每次递归start的值为当前所选值+1class Solution {
private static List> list;
private static List tem;
public List> combinationSum3(int k, int n) {
list = new ArrayList>();
tem = new ArrayList<>();
dfs(k,n,0,0,1);
return list;
}
public void dfs(int k, int n,int sum,int cnt,int start) {
for (int i = start; i < 10; i++) {
if(sum+i > n || tem.size() > k) {
return;
}
tem.add(i);
if(sum+i == n && tem.size() == k) {
List tem0 = new ArrayList<>();
tem0.addAll(tem);
list.add(tem0);
tem.remove(tem.size()-1);
return;
}
dfs(k,n,sum+i,cnt+1,i+1);
if(tem.size() > 0) {
tem.remove(tem.size()-1);
}
}
}
}
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
