combination sum2的问题

发信人: taar (taar), 信区: JobHunting
标  题: combination sum2的问题
发信站: BBS 未名空间站 (Sun Dec 28 01:50:08 2014, 美东)

测试：
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

下面的代码是对的。
但是我就 不明白    if (num[i]!=pre) 是怎么保证 没有重复使用一个数字的呢。
我认为 反而会导致［1，1，6］ 这种结果出问题，奇怪的是没有出问题
求教！

void dfs(vector<int>const &num, int target, vector<vector<int> > &res,
vector<int> &r,int st){
        if (target<0){
            return;
        }else{
            if (target==0){
                res.push_back(r);
            }else{
                int pre = -1;
                for (int i=st;i<num.size();i++){
                    if (num[i]!=pre){
                        r.push_back(num[i]);
                        dfs(num,target-num[i],res,r,i+1);
                        pre = num[i];
                        r.pop_back();
                    }
                }
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
                // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        if (num.size()==0){return res;}
        sort(num.begin(),num.end());
        vector<int> r;
        dfs(num,target,res,r,0);
        return res;
    }
--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 74.]

http://www.mitbbs.com/article_t/JobHunting/32857225.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东品牌街，千万京东优惠券免费领 ， 更多京东优惠券