1、题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。?
2、算法分析
典型的回溯算法题型。
回溯算法题型有：组合、排序、子集、切割、棋牌等等。
先说下什么是回溯算法：回溯算法是基于递归的。而算法的整体思想基于N叉树的遍历。
回溯思想大概借助N叉树的子节点向父节点回溯。
回溯算法按步骤：
①确定回溯函数的参数：
- targetSum（int）目标和，也就是题目中的n。
- k（int）就是题目中要求k个数的集合。
- sum（int）为已经收集的元素的总和，也就是path里元素的总和。
- startIndex（int）为下一层for循环搜索的起始位置。
②确定递归终止条件
path.size() 和 k相等了，就终止。
③单层搜索过程
for循环是对树的宽度进行遍历，递归是对树的深度进行递归。
题目中要求的是求k个数字的和为n
path.add(i); // 求和 sum += i; backTracking(targetSum, k, i + 1, sum); //回溯 path.remove(path.size() - 1); //回溯,找父结点进行下一组的组合求和 sum -= i;
3、代码实现
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n,k,0,1);
return result;
}
public void backTracking(int targetSum,int k,int sum,int startIndex){
// sum > 目标和的时候，不符合条件
if(sum > targetSum){
return;
}
// 相等说明找到一组符合条件的
if(path.size() == k){
if(sum == targetSum){
result.add(new ArrayList<>(path));
return;
}
}
// 遍历
for(int i = startIndex;i <= 9 - (k - path.size()) + 1;i++){
path.add(i);
// 求和
sum += i;
// 每求一次和 比较一次
backTracking(targetSum,k,sum,i+1);
// 回溯
path.remove(path.size() - 1);
sum -= i;
}
}
}