📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2690| 回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

Combination sum 1 and 2

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
为什么time complexity是 n!? 我觉得是2^n 啊? 求教!


public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> item = new ArrayList<Integer>();
        if(candidates==null || candidates.length==0){
            return result;
        }
        Arrays.sort(candidates);
        helper(candidates,target,0,0,result,item);
        return result;
    }

    private void helper(int[] cand, int target, int sum, int index, List<List<Integer>> result, List<Integer> item){
        if(sum==target){
            result.add(new ArrayList<Integer>(item));
            return;
        }
        if(sum>target){
            return;
        }
        for(int i=index;i<cand.length;i++){
            if(i>0 && cand[i]==cand[i-1]) continue;
            item.add(cand[i]);
            helper(cand,target,sum+cand[i],i,result,item);
            item.remove(item.size()-1);
        }

    }
}




上一篇:Lintcode题目 Continuous Subarray Sum II 有几个test过不了
下一篇:回溯法 = DFS吗?
推荐
stellari 2015-7-6 14:26:58 | 只看该作者
全局:
本帖最后由 stellari 于 2015-7-6 14:28 编辑

这样吧,我给一个估计。不是严格证明,但是应该差不多:
假设target = T, A中的元素是A0, A1, A2, A3, ..., AN,其中总有A0 = 1(为了保证A1~AN的任何一个和<K的组合都能够成立).
那么对任一N维向量k = (k1, k2, ..., kN)
如果其满足
ki > 0 且
k1*A1 + k2*A2 + ... + KN*AN <= T
那么k就是combination sum的一组解。

而k1*A1 + k2*A2 + ... + KN*AN <= T在k所在的向量空间内定义了一个N维的simplex(即三角形,四面体的多维情况)。比如N = 3, A = [1, 2, 3], T = 100. 那么1*k1 + 2*k2 + 3*k3 <= 100在三维空间中定义了一个四面体,该四面体和3坐标轴分别交于(100, 0, 0), (0, 100/2, 0), (0, 0, 100/3)。推广至N维情况,交点则分别为v1 = (T/A1, 0, 0, ... 0), v2= T(0, T/A2, 0 ,.... 0), ... v3 = T(0, ... , T/AN)。它们共同构成了一个对角矩阵:
S = [v1' v2' ... vN'] = T*I*(1./A)
这样的一个simplex的体积有公式得:
1/N! * det|T*I*(1./A)|
其中det|... |表示行列式。

而 det|T*I*(1./A)| = T^N/prod(A) , 即T的N次方除以A中所有元素乘积的倒数,所以simplex的体积为

T^N/(N!*prod(A))

而对于较大的simplex,其中的整数坐标点的个数在数值上近似与其体积相等。因此该程序的时间复杂度应该近似为

f(N, T) ~ T^N / (N! * prod(A))

如果当T很大,而A中元素都很小时,可以看做O(T^N)。
回复

使用道具 举报

全局:
pyx115 发表于 2015-7-6 06:45
LZ想说是 N^2? N! 就是 N^2 啊

神回复啊神回复~
回复

使用道具 举报

推荐
stellari 2015-7-6 12:58:38 | 只看该作者
全局:
本帖最后由 stellari 于 2015-7-6 13:04 编辑
douya 发表于 2015-7-6 11:55
您好,
多谢回复!
我想问的是combination sum I, II. 不是combinations。 不过应该都是2^n 吧。

Oops,不好意思,看错了题目。如果是这两道题的话,时间复杂度肯定不仅仅是数组长度N的函数,而是N, K(K为Target)的二维函数。设想[1,2,3], 10和[1,2,3], 1000这两个例子。后者的搜索时间远大于前者。如果数组中包含的数据恰为[1~N]这N个数,且K大于N时,可以证明时间复杂度应在O(K^N)水平。但是K^N只是个比较松的上界。至于是否有更逼近的上界暂时我还证不出来。

评分

参与人数 1大米 +1 收起 理由
glad2mu + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
pyx115 2015-7-6 06:45:06 | 只看该作者
全局:
LZ想说是 N^2? N! 就是 N^2 啊
回复

使用道具 举报

🔗
 楼主| douya 2015-7-6 07:49:15 | 只看该作者
全局:
pyx115 发表于 2015-7-6 06:45
LZ想说是 N^2? N! 就是 N^2 啊

我觉得是2^n啊
感觉是T(n) = T(n-1) + T(n-2)+....T(1)
回复

使用道具 举报

🔗
stellari 2015-7-6 09:14:43 | 只看该作者
全局:
就是O(2^N),准确说是O(N*2^N)。见下帖讨论:

http://www.1point3acres.com/bbs/thread-117602-1-1.html
回复

使用道具 举报

🔗
 楼主| douya 2015-7-6 11:55:50 | 只看该作者
全局:
stellari 发表于 2015-7-6 09:14
就是O(2^N),准确说是O(N*2^N)。见下帖讨论:

http://www.1point3acres.com/bbs/thread-117602-1-1.html

您好,
多谢回复!
我想问的是combination sum I, II. 不是combinations。 不过应该都是2^n 吧。
回复

使用道具 举报

🔗
 楼主| douya 2015-7-7 09:05:05 | 只看该作者
全局:
stellari 发表于 2015-7-6 14:26
这样吧,我给一个估计。不是严格证明,但是应该差不多:
假设target = T, A中的元素是A0, A1, A2, A3, ... ...

我再看看这个证明。
回答这么细,
非常感谢您啊!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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