6
#yyds干货盘点# leetcode算法题:组合总和 II
source link: https://blog.51cto.com/u_13321676/5429252
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# leetcode算法题:组合总和 II
原创给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
[1,1,6],
[1,2,5],
[1,7],
[2,6]
输入: candidates = [2,5,2,1,2], target = 5,
[1,2,2],
代码实现:
class Solution {
List<int[]> freq = new ArrayList<int[]>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> sequence = new ArrayList<Integer>();
public List<List<Integer>> 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 void dfs(int pos, int rest) {
if (rest == 0) {
ans.add(new ArrayList<Integer>(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);
}
}
}
List<int[]> freq = new ArrayList<int[]>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> sequence = new ArrayList<Integer>();
public List<List<Integer>> 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 void dfs(int pos, int rest) {
if (rest == 0) {
ans.add(new ArrayList<Integer>(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);
}
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK