盒子
盒子
文章目录
  1. 39. 组合总和

39_组合总和_leetcode

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:所有数字(包括 target)都是正整数。解集不能包含重复的组合。

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

题解: 回溯算法+剪枝,关键在于栈与递归巧妙应用

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
32
33
34
/**
* 回溯 + 剪枝
*/
public class Solution {

private List<List<Integer>> res = new ArrayList<>();
private int[] candidates;
private int len;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length <= 0) {
return res;
}

Arrays.sort(candidates);
this.len = candidates.length;
this.candidates = candidates;
findCombinationSum(target, 0, new Stack<>());
return res;
}

private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
if (residue == 0) { // 进行结算,即找到解
res.add(new ArrayList<>(pre));
}
// residue - candidates[i] >= 0 剪枝小于0的解
for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
pre.add(candidates[i]);
// 因为candidates 中的数字可以无限制重复被选取,故仍然取i
findCombinationSum(residue - candidates[i], i, pre);
pre.pop();
}
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫