Leetcode 216.组合总和III

题目

思路

题目说只使用数字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)