题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：回溯
思路：
代码示例：（Java）
public class Solution1 {
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);
}
}
}
复杂度分析
考察知识点
1.递归+回溯
