LeetCode-040-组合总和|LeetCode-040-组合总和 II
组合总和 II
题目描述:给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。解法一:回溯算法
【LeetCode-040-组合总和|LeetCode-040-组合总和 II】candidates 中的每个数字在每个组合中只能使用一次。
说明:
示例说明请见LeetCode官网。
- 所有数字(包括目标数)都是正整数。
- 解集不能包含重复的组合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
- 首先,将原数组排序;
- 然后,声明一个数组freq用来记录每个不同的数字出现的次数;
- 然后,用回溯算法递归判断处理的序列是否符合条件,将符合条件的序列添加到结果集中,最后返回所有符合条件的结果集。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LeetCode_040 {
/**
* 记录每个不同的数字出现的次数
*/
private static List freq = new ArrayList<>();
/**
* 符合条件的结果集
*/
private static List> ans = new ArrayList<>();
/**
* 匹配的序列
*/
private static List sequence = new ArrayList<>();
/**
* 回溯算法
*
* @param candidates
* @param target
* @return
*/
public static List> combinationSum2(int[] candidates, int target) {
// 首先将给定的数组排序
Arrays.sort(candidates);
for (int num : candidates) {
int size = freq.size();
if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
freq.add(new int[]{num, 1});
} else {
++freq.get(size - 1)[1];
}
}
dfs(0, target);
return ans;
}public static void dfs(int pos, int rest) {
if (rest == 0) {
/**
* 如果当前的和已经等于target了,将当前的序列添加到结果集
*/
ans.add(new ArrayList(sequence));
return;
}
if (pos == freq.size() || rest < freq.get(pos)[0]) {
/**
* 如果已经遍历完所有的数字或者待处理的数小于下一个要匹配的数字,则当前的序列不符合条件,返回
*/
return;
}dfs(pos + 1, rest);
int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
for (int i = 1;
i <= most;
++i) {
sequence.add(freq.get(pos)[0]);
dfs(pos + 1, rest - i * freq.get(pos)[0]);
}
for (int i = 1;
i <= most;
++i) {
sequence.remove(sequence.size() - 1);
}
}public static void main(String[] args) {
int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
for (List integers : combinationSum2(candidates, 8)) {
for (Integer integer : integers) {
System.out.print(integer + " ");
}
System.out.println();
}
}
}
【每日寄语】 登高望远,不是为了被整个世界看到,而是为了看到整个世界。
推荐阅读
- 21天|21天|羊多多组合《书都不会读,你还想成功》
- 2018-08-29|2018-08-29 - 草稿 - 草稿
- R语言|R语言 函数
- 急需解答一个组合题
- 21天|21天 书香美妈组合?魔鬼老大,天使老二?
- 175.|175. 组合两个表(SQL)
- 我谈小组合作
- 15.三数之和为0的所有组合
- 说说我的3unshine(原sunshine组合)入坑史
- 21天|21天|书香美妈组合 《如何说 孩子才能和平相处》