leetcode 算法-组合总和 III

leetcode 传送门

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

解题思路

首先，我们很容易有这样一个想法,构造一棵树,根节点为0,子节点为1到,然后每个子节点的子节点都是1-9,我们只需要累加子节点以及子孙节点的值,然后判断其和是否等于目标值n并且深度等于k即可得出所有组合。这是最简单的思想，虽然问题很多。但是提供了一个开始的思路，接下来只需要优化这个算法就行了。

首先这题要求组合不能重复,于是,我们可以再加一个要求,从深度为2的节点开始,子节点的个数为9-父节点值,值分别为父节点值到9,这样就可以保证从根到叶子不存在重复的路径。

接下来,我们只需要在这棵树中寻找我们需要的从深度为1的节点到叶子节点的路径即可,这题很明显我们应该使用深度优先遍历, 然后依次遍历子节点,子节点的子节点,用一个变量累加其和,如果深度等于k而且和正好为n,则添加到解空间中。如果深度大于k,或者和大于n,则回溯即可。

代码

class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); find(result, new ArrayList<>(), n,1,k); return result; } public static void find(List<List<Integer>> listAll, List<Integer> tmp, int target, int num,int k) { // 递归的终点 if (target < 0)return; if(k==0){ if (target == 0) listAll.add(tmp); return; } // 遍历 for (int i = num; i < 10 && i <= target; i++) { // 深拷贝tmp List<Integer> list = new ArrayList<>(tmp); list.add(i); // 递归运算，将i传递至下一次运算是为了避免结果重复。 find(listAll, list, target - i, i+1,k-1); } } }