-
Notifications
You must be signed in to change notification settings - Fork 1
/
39. Combination Sum
99 lines (88 loc) · 4.03 KB
/
39. Combination Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
39. Combination Sum
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
// 此题time complexity无比蛋疼
// (1) 首先来看Combination sum I和II的区别:
// Combination sum 的input无dups, 但是input的元素可以重复利用
// Combination sum II 的input有重复, 但是input的元素只能用一次
//
// (2) 其次, 弄明白 Combination sum II的time complexity是怎么一回事儿
// https://github.com/Deadbeef-ECE/Interview/blob/master/Leetcode/BackTracking/040_Combination_Sum_II.java
// O(k * 2^n) time:
// 每个解的长度平均为k, copy list的时间复杂度是O(k)
// 解空间:
// 因为元素只能用一次, 所以对于长度是k的解, 解的个数最多是C(n,k)个, 而一般情况下,
// 解的个数远小于C(n,k), 那么问题来了, 对于长度为k的解, worst case是什么?
// int[] arr = {1,1,1,1,1,1,1,1,1,1} target = 2 这时候解的个数才达到C(n,k),
// 注意: 即便在ret.add之前要去重, 我们也是在找到了可行解之后再检查是否是重复解, 所以
// 解空间树是包含重复解的, 所以时间复杂度也包括这些重复解
//
// 还有一点是, 题解的长度并不是固定的, 也就是k可能有多个, 所以可能是C(n,0) ~ C(n,n)
// 中的多个之和, 而我们知道C(n,0) + C(n,1) + C(n,2) + ... C(n,n) = 2^n
// 所以可以把时间复杂度算成O(k * 2^n)
// O(k * 2^n') time:
// 此题可以转换成 combination sum II, 如何做呢, 举个栗子:
// int[] arr = {2, 3, 4, 5, 6}, target = 10; 我们知道此题中,每个元素可以重复用,
// 其实, 如果把 arr 变成 {2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6}, 然
// 后每个元素只能用一次, 就变成了combination sum II的要求了.
// 我们再看新数组, 元素多了很多, 多了多少?
// 那就是数组中所有小于等于target的元素E增加了ceil(target/E)个, 然后就可以用
// combination sum II的方法分析复杂度了. 这里n'是新arr的大小
// O(n) space:
// one n is the recursion stack
// another n is used when copying list
// Both of them depend on the longest solution which is equal to
// target/(min in candidates) in this problem(可以再看下上面的例子, n就是新
// arr中2的个数, 为ceil(10/2))
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
dfs(result,new ArrayList<>(),candidates,target,0);
return result;
}
void dfs(List<List<Integer>> result, List<Integer> list, int[] candidates ,int target,int pos){
if(target<0) return;
if(target==0){
result.add(new ArrayList<>(list));
return;
}
for(int i = pos ; i< candidates.length ; i++){
list.add(candidates[i]);
dfs(result,list,candidates,target-candidates[i],i);
list.remove(list.size()-1);
}
}
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
public int combinationSum4(int[] nums, int target) {
int[] comb = new int[target + 1];
comb[0] = 1;
for (int i = 1; i < comb.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i - nums[j] >= 0) {
comb[i] += comb[i - nums[j]];
}
}
}
return comb[target];
}
Follow-up
What if negative numbers are allowed in the given array?
Then adding a num to the combination is not guaranteed to be increasing, which means I can add a huge bounch of negative nums
and add a huge bounch of positive nums to achieve a target sum.
eg.target=0:[-1,1],[-1,-1,1,1],[-1,-1,-1,1,1,1]...
How does it change the problem?
We will have lots of lots of possible combinations, even infinity.
What limitation we need to add to the question to allow negative numbers?
For example, each negative num can only be used once, etc.