首页 > 代码库 > LeetCode--Combination Sum --ZZ
LeetCode--Combination Sum --ZZ
http://blog.csdn.net/linhuanmars/article/details/20828631
这个题是一个NP问题，方法仍然是N-Queens中介绍的套路。基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的。Java代码如下：
1 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { 2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); 3 if(candidates == null || candidates.length==0) 4 return res; 5 Arrays.sort(candidates); 6 helper(candidates,0,target,new ArrayList<Integer>(),res); 7 return res; 8 } 9 private void helper(int[] candidates, int start, int target, ArrayList<Integer> item, 10 ArrayList<ArrayList<Integer>> res)11 {12 if(target<0)13 return;14 if(target==0)15 {16 res.add(new ArrayList<Integer>(item));17 return;18 }19 for(int i=start;i<candidates.length;i++)20 {21 if(i>0 && candidates[i]==candidates[i-1])22 continue;23 item.add(candidates[i]);24 helper(candidates,i,target-candidates[i],item,res);25 item.remove(item.size()-1);26 }27 }
注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。这道题有一个非常类似的题目Combination Sum II，有兴趣的朋友可以看看，一次搞定两个题哈。
LeetCode--Combination Sum --ZZ
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。