M**********l
发帖数: 68 | 1 上周二面的，就是combination sum, 但是数组里面可能包含negative number, 所以和
LC上面的不完全一样，这里有讨论：
http://stackoverflow.com/questions/15532957/to-find-a-subset-fr
我先直接对每个combination然后求和比较，复杂度就是n^2*2^n，想着可以再改进，但
是没给机会，看来还是要第一时间就把最优解给说出来。整个过程20多分钟。
求明天g家onsite bless. | t**r
发帖数: 3428 | 2 public class Solution {
private List> ret;
private List curList;
public List> combinationSum2(int[] candidates, int target)
{
ret = new ArrayList>();
curList = new ArrayList();
Arrays.sort(candidates);
getSum(candidates,target,0);
return ret;
}
private void getSum(int[] candidates, int target, int lastIndex){
if(target == 0){
ret.add(new ArrayList(curList));
} else {
int i = lastIndex;
while(i < candidates.length){
int candidate = candidates[i];
curList.add(candidate);
getSum(candidates, target-candidate, i+1);
curList.remove(curList.size()-1);
while( (i< (candidates.length-1)) && (candidates[i]==
candidates[i+1])){
i++;
}
i++;
}
}
}
}
这样不就行了，怎么会那么难？ | l*****z
发帖数: 3022 | | A*******e
发帖数: 2419 | 4 我先直接对每个combination然后求和比较，复杂度就是n^2*2^n
没看懂你在说什么。
另外最优解是啥？你给那个link质量似乎不高啊。 |
|
