1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ans = new ArrayList<>();
helper(ans, new ArrayList<>(), candidates, 0, target);
return ans;
}
private void helper(List<List<Integer>> ans, List<Integer> curr, int[] candidates, int pos, int remain) {
if (remain == 0) {
ans.add(new ArrayList<>(curr));
return;
}
for (int i = pos; i < candidates.length && candidates[i] <= remain; i++) {
if (i > pos && candidates[i] == candidates[i - 1]) {
continue;
}
curr.add(candidates[i]);
helper(ans, curr, candidates, i + 1, remain - candidates[i]);
curr.remove(curr.size() - 1);
}
}
}
|
递归函数是pos标记的位置及以后的元素中去凑remain, curr装的是目前已经凑的东西, 我们的目的是凑够remain再带上curr里的, 就能凑到target. for循环表示选择pos后的每一个位置作为当前的head然后去凑remain, 最后凑成的数字们前面加上curr的那些元素即可. 这里我们的操作是直接在curr里面加然后再及时取出来即可, 这也是backtrack的常规操作. 15行的if判断就是不能让同一个元素做两次head.
后来的想法总结:
我本来是想着每个位置的数字存在包括和不被包括两种状态. 然后我们遍历所有情况即可. 但是这种方式没办法避免duplicates或者很麻烦. 于是就有了这道题的解法. 我们从pos及以后的位置让每个元素都来做start然后去凑remain, 但是相同值的元素只能做一次. 大概就是这样.
时间复杂度: O(2^n) 因为让每个元素轮流做head的意思也就是不选该元素之前的所有元素. 原理和我们的想法是一样的.
空间复杂度: O(n)
