LeetCode:40. 组合总和 II(回溯 + 剪枝 Java)
目录
40. 组合总和 II
题目描述:
实现代码与解析:
回溯 + 剪枝
原理思路:
40. 组合总和 II
题目描述:
给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [[1,2,2],[5]]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
实现代码与解析:
回溯 + 剪枝
class Solution {
private List<Integer> path = new ArrayList();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates, 0, target, 0);
return res;
}
public void dfs(int[] candidates, int cur, int target, int idx) {
if (cur == target) {
res.add(new ArrayList<>(path));
return;
}
if (idx >= candidates.length) return;
if (cur + candidates[idx] > target) return; // 如果大于,剪枝
for (int i = idx; i < candidates.length; i++) {
if (i > idx && candidates[i] == candidates[i - 1]) { // 同一位置不能重复选相同的数
continue;
}
path.add(candidates[i]);
dfs(candidates, cur + candidates[i], target, i + 1);
path.remove(path.size() - 1); // 回溯
}
return;
}
}
原理思路:
比较简单啊,看代码吧。回溯题。