Q39 组合总和(combination-sum)

解析思路

leetcode 中等难度,题目描述点击这里

标准的回溯类题目,对于回溯类题目,通常都是要穷举所有的情况,然后判断那些情况是符合题目要求的。

然后穷举通常是通过深度优先搜索(dfs)来实现的,我们可以先将结果展开成一棵树,然后再根据这棵树来写代码,就比较好理解,如下图:

以[2,3,5],8 为例:

展开

上图只对最左边的路径进行了完全展开(全部展开太麻烦了)

总的来说回溯就是不断的进行尝试,如果尝试到最后发现不满足要求那就换一个路径继续尝试,属于暴力算法。因此此类题目的数据规模通常会限制的比较小。

另外通常还能根据题目的要求来做剪枝操作,减少一些不必要的运算。

比如本题可以先将数组排序,当选择的某个数已经大于目标值时,就没必须选择这个数的下一个数继续尝试了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Q39 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
//排序
Arrays.sort(candidates);
dfs(candidates, target, 0, new Stack<>(), res);
return res;
}

private void dfs(int[] candidates, int target, int index, Stack<Integer> temp, List<List<Integer>> res) {
if (target == 0) {
//说明找到一个结果序列
res.add(new ArrayList<>(temp));
return;
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] > target) {
//前面已经排序过,所以在这里可以进行剪枝操作,如果candidates[index]都小于target了,那就不需要比较后面的了,肯定不满足要求
return;
}
temp.push(candidates[i]);
//注意这里,为了让结果集不重复,选择重复元素时只能对当前元素进行重复选择,不能重复选择之前的元素。所以递归的index为i,不是0
dfs(candidates, target - candidates[i], i, temp, res);
temp.pop();
}
}

public static void main(String[] args) {
new Q39().combinationSum(new int[]{2, 3, 5}, 8).forEach(System.out::println);
}
}
本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号