一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2625|回复: 11
收起左侧

[Leetcode] Combination sum 迭代

[复制链接] |试试Instant~ |关注本帖
hfzhangql 发表于 2014-11-3 05:35:37 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Combination sum 迭代怎么写,谁有代码给个链接看看?


补充内容 (2014-11-3 23:55):
谢谢各位的回复,这题用recursion比较简单而且直观。我现在是想问下有没有iteration的,用dp的思想来解的,时间复杂度应该是在O(n^2)

评分

1

查看全部评分

nibuxing 发表于 2014-11-3 06:10:52 | 显示全部楼层
表示也刚刷到这道题,用recursion挺方便的啊,包括八皇后,subset,permutations都用recursion的套路我觉得很好用。
回复 支持 反对

使用道具 举报

flyaway25 发表于 2014-11-3 07:27:15 | 显示全部楼层
这个随便一搜都有吧,思路就是用recursion,只有sum等于target的时候才要返回结果。
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2014-11-3 12:08:15 | 显示全部楼层
本帖最后由 Freetymekiyan 于 2014-11-2 23:14 编辑

其实这个思路应该叫backtracking
  1.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  2.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  3.         Arrays.sort(candidates); // sort the array
  4.         recurse(new ArrayList<Integer>(), target, candidates, 0, result);
  5.         return result;
  6.     }

  7.     /**
  8.      * do it recursively
  9.      */
  10.     private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> result) { // list is one of the answers
  11.         if (target == 0) {
  12.             result.add(list);
  13.             return;
  14.         }
  15.         for (int i = index; i < candidates.length; i++) {
  16.             int newTarget = target - candidates[i]; // subtract candidate from target
  17.             if (newTarget >= 0) {
  18.                 List<Integer> copy = new ArrayList<Integer>(list); // create a copy
  19.                 copy.add(candidates[i]);
  20.                 recurse(copy, newTarget, candidates, i, result); // see if there is more
  21.             } else { // run out of target
  22.                 break;
  23.             }
  24.         }
  25.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| hfzhangql 发表于 2014-11-3 23:52:24 | 显示全部楼层
nibuxing 发表于 2014-11-3 06:10
表示也刚刷到这道题,用recursion挺方便的啊,包括八皇后,subset,permutations都用recursion的套路我觉得 ...

recursion的复杂度是O(2^n),面试的时候follow up要优化就挂了
回复 支持 反对

使用道具 举报

 楼主| hfzhangql 发表于 2014-11-3 23:52:56 | 显示全部楼层
flyaway25 发表于 2014-11-3 07:27
这个随便一搜都有吧,思路就是用recursion,只有sum等于target的时候才要返回结果。

如果不用recursion怎么写呢,recursion复杂度太高
回复 支持 反对

使用道具 举报

 楼主| hfzhangql 发表于 2014-11-3 23:53:42 | 显示全部楼层
Freetymekiyan 发表于 2014-11-3 12:08
其实这个思路应该叫backtracking

有没有iteration,用dp思想的代码啊?
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-11-4 01:39:02 | 显示全部楼层
本帖最后由 Adeath 于 2014-11-4 01:55 编辑

我觉得DP不适合这道题,DP比较少用来发现全部答案的集合,通常是发现数量。一个集合的combination,每个元素都有可能出现或者不出现,也就是说worst case复杂度就是2^n, 不可能做到n^2的。
回复 支持 反对

使用道具 举报

Freetymekiyan 发表于 2014-11-4 03:23:06 | 显示全部楼层
本帖最后由 Freetymekiyan 于 2014-11-3 14:25 编辑
Adeath 发表于 2014-11-3 12:39
我觉得DP不适合这道题,DP比较少用来发现全部答案的集合,通常是发现数量。一个集合的combination,每个元 ...

你说的很对,DP在这里并不适用。

combination sum或者subset sum要想象所有的解空间是一颗树,每个节点的值是当前子集加起来的和,要遍历这个解空间得到答案。比如说{1, 2, 3},3
                         0
             1                      0                     (with 1 or without 1)
        3        1            2        0                (with 2 or without 2)
    6    3    4    1    5    2    3    0             (with 3 or without 3)

backtracking已经是最好的思想了,一旦不符合条件就尝试其他分支。树的节点有2^n个,最坏情况遍历整棵树,逃不开2^n的。



回复 支持 反对

使用道具 举报

 楼主| hfzhangql 发表于 2014-11-4 11:34:56 | 显示全部楼层
Adeath 发表于 2014-11-4 01:39
我觉得DP不适合这道题,DP比较少用来发现全部答案的集合,通常是发现数量。一个集合的combination,每个元 ...

http://blog.csdn.net/zyfo2/article/details/8592955
这里有个
回复 支持 反对

使用道具 举报

Adeath 发表于 2014-11-4 12:43:55 | 显示全部楼层
hfzhangql 发表于 2014-11-4 11:34
http://blog.csdn.net/zyfo2/article/details/8592955
这里有个

我个人观点  你非要用DP当然也不是不可以。。。 overall O(n*target) 但每次更新dp[]都要把前面的解读出来,而前面解的数量是很可能呈指数增长的  所以不论从时间 空间复杂度上都没有很大的优势
而且你也看到了 用DP算解的数量多么neat  算解的全集不可避免要ugly。。  
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2015-4-12 01:30:14 | 显示全部楼层
最近也刷这道题,小挖个坟,提供一个从同学那儿学到的DP的思路。DP应该是有两种情况吧,一个是以当前状态更新之后状态,我提供的思路就是这个;另一个是当前状态用之前的状态计算,类似LCS就是这类。虽然听起来似乎一样但是操作起来不一样。
拿个例子说一下,比如给[2,3,7] target = 7.
首先DP需要一个三维数组DP[][][]保存结果,初始化其长度为1+target,因为其中DP[0]的结果需要初始化为[]。然后就从DP[0]开始增长。
DP[0]: []
从左扫到右,0+2和0+3是小于target的,0+7刚好是target,于是更新为:
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[7]: [7]
接下来找DP[1]发现没有解,跳过,找DP[2],更新为:
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[4]: [2,2]
DP[5]: [2,3]
DP[7]: [7]
以此类推,最后用DP[target-1]更新完之后,DP[target]就是想要的结果。
不过假设candidates的长度是n,DP中最长的解集个数是m,那么时间复杂度和空间复杂度都是O(n*m*target)了。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表