题目
思路
题目说只使用数字1-9,是k个数的和
树的宽度是1-9,树的深度是k
1.确定递归函数的返回值及参数:
返回值是void,参数这里还是先设定两个全局变量。一个是path存放符合条件单一结果。如:(1,2)。一个是result,是所有path的集合[(1,2),(1,3)…]。此外局部变量有题目中的n,k。另外还有一个sum参数用来记录遍历过程的和。
2.回溯函数终止条件
当到达叶子节点时结束。也就是path里的数有k个的时候结束。同时要在这里判断在叶子节点时,path里元素之和是否等于n。这里在递归参数的时候用一个sum参数来实现,在递归的时候每到一层加上当前值。
3.单层搜索的过程
用path保存当前节点。
sum+=当前值
搜索当前节点的所有子节点
回溯,remove
代码
//未剪枝
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
int sum = 0;
backtracking(k, n, sum, 1);
return res;
}
public void backtracking(int k, int n, int sum, int startIndex) {
if (path.size() == k) {
if (n == sum)
res.add(new ArrayList<>(path));
else {
return;
}
}
for (int i = startIndex; i <= 9; i++) {
path.add(i); //将当前节点add
sum += i;//加上当前值
backtracking(k, n, sum, i + 1);
path.remove(path.size() - 1);
sum -= i;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)