AlgoPressAppearance
0216-组合总和III
https://leetcode.cn/problems/combination-sum-iii
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
- 2 <= k <= 9
- 1 <= n <= 60
思路
回溯算法，按层遍历 1-9 ， 递归的时候 减小k ， 减小和 ，当k==0 n==0 的时候，返回结果 特别注意： 遍历的时候，
- 不要使用 cur 使用 begin 表示起始数字
- 添加数字到 list 中的时候，千万是要添加 i 而不是 begin 的数字
- 下一个数字是 i + 1 而不是 总之不要是用 cur 作为当前变量，避免混淆, for 循环的时候，压入的list 是 循环里面的数字，而不是传入的 begin
参考代码
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private List<int> CopyList(List<int> list)
{
List<int> newList = new List<int>();
for (int i = 0; i < list.Count; i++)
{
newList.Add(list[i]);
}
return newList;
}
private void dfs(int k, int n, int cur, List<int> list)
{
//Console.WriteLine("check k={0},n={1},cur={2}", k, n, cur);
if (k < 0 || n < 0)
{
return;
}
if (k == 0 && n == 0)
{
//输出
//Console.WriteLine("put to result");
result.Add(CopyList(list));
return;
}
//注意开始的数字是 cur 而不是1，防止重复循环
for (int i = cur; i <= 9; i++)
{
list.Add(i);
dfs(k - 1, n - i, i + 1, list);
list.RemoveAt(list.Count - 1);
}
}
public IList<IList<int>> CombinationSum3(int k, int n)
{
List<int> list = new List<int>();
dfs(k, n, 1, list);
return result;
}
public void Run()
{
CombinationSum3(3, 7);
}
}
修改变量 cur 为 begin ， 避免混淆
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private List<int> CopyList(List<int> list)
{
List<int> newList = new List<int>();
for (int i = 0; i < list.Count; i++)
{
newList.Add(list[i]);
}
return newList;
}
private void dfs(int k, int n, int begin, List<int> list)
{
if (k < 0 || n < 0)
{
return;
}
if (k == 0 && n == 0)
{
//输出
result.Add(CopyList(list));
return;
}
//注意开始的数字是 begin 而不是1，防止重复循环
//注入dfs下一层是 i+1 而不是 begin +1
for (int i = begin; i <= 9; i++)
{
list.Add(i);
dfs(k - 1, n - i, i + 1, list);
list.RemoveAt(list.Count - 1);
}
}
public IList<IList<int>> CombinationSum3(int k, int n)
{
List<int> list = new List<int>();
dfs(k, n, 1, list);
return result;
}
public void Run()
{
CombinationSum3(3, 7);
}
}
思路2： 从第一个数开始
参考代码2
直接从第一个数开始，使用选他或者不选他，递进到第二个数，而不是一开始就循环所有的数
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private List<int> CopyList(List<int> list){
List<int> newList = new List<int>();
for(int i=0; i<list.Count; i++){
newList.Add(list[i]);
}
return newList;
}
private void dfs(int k, int n, int cur, List<int> list){
//Console.WriteLine("check k={0},n={1},cur={2}",k,n,cur);
if(k < 0 || n < 0 ){
return;
}
if(k == 0 && n == 0){
//输出
result.Add(CopyList(list));
return;
}
//最后一个数如果大于9就返回，注意不能在最开始就返回，因为那时候结果还未输出
if(cur > 9){
return;
}
//选他
//Console.WriteLine("add cur = {0}",cur);
list.Add(cur);
dfs(k-1,n-cur,cur+1,list);
list.RemoveAt(list.Count - 1);
//不选他
dfs(k,n,cur+1,list);
}
public IList<IList<int>> CombinationSum3(int k, int n) {
List<int> list = new List<int>();
dfs(k,n,1,list);
return result;
}
}
复习:20220512
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int k, int n, int begin, List<int> list){
if(k == 0 && n==0){ //输出结果，数字个数正好凑成 n
result.Add(new List<int>(list.ToArray()));
return;
}
if(n < 0){
return;
}
for(int i=begin; i<=9; i++){
list.Add(i);
dfs(k-1,n-i,i+1,list); //注意这里传入回溯的begin坐标是i
list.RemoveAt(list.Count-1);
}
}
public IList<IList<int>> CombinationSum3(int k, int n) {
List<int> list = new List<int>();
dfs(k,n,1,list);
return result;
}
}