前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的216题。
问题描述
找出所有相加之和为 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]]
分析：
func min(a, b int) int{
if a < b {
return a
}
return b
}
func combinationSum3(k int, n int) [][]int {
tmp := make([]int, 0)
res := make([][]int, 0)
dfs(k, n, tmp, &res)
return res
}
func dfs(k int, n int, tmp []int, res *[][]int) {
l := len(tmp)
if n < 0 {
return
}
if l == k-1 {
if l >= 1 {
if n > tmp[l-1] && n <= 9 {
//
tmp = append(tmp, n)
t := make([]int, k)
copy(t, tmp)
*res = append(*res, t)
return
}
return
}
//
if n > 9 {
return
}
tmp = append(tmp, n)
t := make([]int, k)
copy(t, tmp)
*res = append(*res, t)
return
}
var i int
if l == 0 {
i = 1
} else {
i = tmp[l-1] + 1
}
end := min(n/(k-l) - (k-l-1)/2 + 1, 9)
for ; i <= end; i++ {
dfs(k, n-i, append(tmp, i), res)
}
}
感觉自己写的不是很好，找到了一个C++的代码，没有优化，便于读者看懂
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> v;
vector<int> vec;
combination(v, vec, k, n, 1);
return v;
}
void combination(vector<vector<int>>& v, vector<int>& vec, int k, int n, int start) {
if (vec.size() == k && n == 0) {
v.push_back(vec);
return;
}
for (int i = start; i <= 9; i++) {
vec.push_back(i);
combination(v, vec, k, n - i, i + 1);
vec.pop_back();
}
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
