题目
组合总和 III 216题
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。 复制代码
分析
其实大家可以看看这题，也是用回溯算法解决的，最近几天，六六分享的都是回溯算法的，关于回溯算法的定义啥的，可以看上面那篇文章，这边我们就直接把模版拿出来，大家就像填词一样，往里面填代码试试，
模版
回溯三部曲
- 1.确定回溯单层逻辑
通过for循环控制当前位置（也就是当前递归层）的数字可以从1选到9，每选择一个数字（for每遍历到一个数字）我们就从目标总和中减去它的值，同时把他加入记录数字组合的集合中； 通过上一步我们就确定了第一位数字，接下来通过递归确定下一位数字，要注意的是需要更新下一层递归选择下一位数字时开始的位置，因为上一层选过的数字下一层就不能再选了； 当递归到某层时，我们发现此时已经确定了k个数字了，需要判断这k个数的和是否等于n，如果等于n，则把这次收集到的组合加入最终的结果集并终止当前层递归，准备回溯；反之，直接终止递归，准备回溯； 当我们从上一层递归中出来后，就该回溯了，即删掉最后一位的数字重新选择一个新数字；
- 2.确定回溯函数参数以及返回值
根据上述分析，可以得知我们在每层的递归中都会更新目标总和的值、判断当前是否选够了k个数字、以及我们必须直到当前这层递归中选择数字的起点在哪里 因此参数需要：目标总和、题目给出的k、当前层递归选择数字的起始位置 因为我们将用两个全局变量记录当前组合以及最终结果集，所以不需要返回值
- 3.确定回溯函数终止条件
在分析单层逻辑时，我们就已经得到：当我们选取了k个数字后们就一个终止当前递归返回了
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } } 复制代码
题解
package com.six.finger.leetcode.five; /* 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件： 只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。 输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。 */ import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class fifteen { public static void main(String[] args) { combinationsum(9, 45); } public static List<List<Integer>> combinationsum(int k, int n) { List<List<Integer>> res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); backtracking(res, path, k, n, 1); return res; } private static void backtracking(List<List<Integer>> res, LinkedList<Integer> path, int k, int n, int i) { int sum = 0; //第一步，递归的退出条件 for (Integer integer : path) { sum = sum + integer; } if (sum > n) { return; } if (sum == n && path.size() == k) { res.add(new ArrayList<>(path)); return; } //第二步 树的横向长度，和减枝活动 for (int j = i; j <= 9 - (k - path.size()) + 1; j++) { path.add(j); backtracking(res, path, k, n, j + 1); path.removeLast(); } } } 复制代码
一看提交记录，我去太菜了，想想怎么优化下
优化
其实就是，我为啥每次都要计算path的和，改下,把这样计算
for (int j = i; j <= 9 - (k - path.size()) + 1; j++) { sum=sum+i; path.add(j); backtracking(res, path, k, n, j + 1,sum); path.removeLast(); sum=sum-i; } 复制代码
然后并没有什么用哦
结束
好了，今天这题就结束了，我发现连续的去练一种类型，其实这种题就慢慢的没那么难了，以前我总觉得算法很难，但是其实万事万物，都有其自然的规律，我们只能善于总结，虽然创造不出什么新的东西，但是还是可以把别人的经验学习到的，加油！！
