39、组合总和
https://leetcode-cn.com/problems/combination-sum/
题目：
题解：
此题要求给定数组中，任意组合数组元素的和等于target，返回所有符合条件的组合。并且数组元素可以重复的使用，但是最后得出的组合中不能有重复的。
首先，要想得出所有符合条件的组合，就要用的经典的回溯模型。
去重复的关键在于，每层递归都不会使用上一层递归使用过的数组元素。
递归回溯减元素得组合，去重关键不要走老路。
AC题解：https://leetcode-cn.com/problems/combination-sum/solution/fei-chang-xiang-xi-de-di-gui-hui-su-tao-lu-by-re-2/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates.length == 0 || target < 0) {
return result;
}
List<Integer> list = new ArrayList<>();
bfs(candidates, target, list, 0);
return result;
}
public void bfs(int[] candidates, int target, List<Integer> list, int start) {
if(target == 0) {
result.add(new ArrayList<>(list));
} else if (target < 0) {
return;
}
for(int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
bfs(candidates, target - candidates[i], list, i);
list.remove(list.size() - 1);
}
}
}
|
上一篇：40-组合总和 ||
下一篇：5、日志服务器的搭建
