Lexi's Leetcode solutions

[leetcode] Combination Sum | 给个数组,找里面能求和=x的所有组合(数字可以重复使用)

Posted on: October 9, 2013

比如{2, 3, 6, 7},x = 7,组合就是{2, 2, 3}和{7}。不能有重复,且必须是sorted order。

这个是标准DFS,一定要记住。先sort array,然后试图用2,用了2之后x相当于只剩5,然后下一层递归再用2,用到没法再用为止(当前值比x还大)。失败后stack pop出来,再试着在前面用了2, 2, 2的条件下用3, 挂,pop出2,在22的条件下用3,正好,输出。然后再pop一个2,再用3, {2, 3},再用下一个3。。在脑子里想一下和树的dfs的图是一样的。

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  Arrays.sort(candidates);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(candidates, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target) //这时候break可以保证不要再查后面那些越来越大的
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i, path, result); //start永远不会越界,所以一开始不用check
    path.pop();
   }
 }
Advertisements

7 Responses to "[leetcode] Combination Sum | 给个数组,找里面能求和=x的所有组合(数字可以重复使用)"

这个可以看成是换硬币吗?用dp做。

不懂唉,怎么用换硬币的方法做?

回的好快啊,多谢。
我的想法是把数组里面的值当成硬币的面值,那么问题就是求指定数额的钱的兑换方法。
for(int i=0; i<candidates.length; i++){
for(int j=candidates[i]; j<=target; j++){
dp[j] += dp[j-candidates[i]];
}
}
但是只能算出target总共有多少兑换法,不能输出具体的兑换方法。你的方法还是最优的。

喔喔,dp一般都是用来算count或者极值的,这样要求返回一个list的,肯定不能用dp,数据量太大啦~

是啊,这么一想清楚多了。
多谢你啦。

代码窗口有没有水平滑动条啊,横排代码太长读不全

list.addAll(path); // It’s confusing
一点小问题:
java iterator的设计问题导致stack不是倒序(LIFO)而是正序添加,所以结果是正确的
http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4475301
你的文章很有帮助 谢谢!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: