LeetCode题目:Combination Sum II

By | 2012 年 9 月 16 日

题目和Combination Sum差不多,加了限制,候选参数中的数字只能使用一次。
还是动态规划,利用两个数组来回倒腾。
其中还是发现了不少问题:

  1. unique和erase的用法
    result.erase(unique(result.begin(),result.end()),result.end());
  2. 细心检查语法



Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
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]


代码
1432ms过大测试集合

class Solution {
public:
    vector > combinationSum2(vector &num, int target) {
        if(num.size() == 0)
            return vector >();
        sort(num.begin(),num.end());
        vector > > *pR = new vector > >(target + 1);
        vector > > *pT = new vector > >(target + 1);
        //initialize
        {
            int c0 = num[0];
            if(c0 > 0 && c0 <= target)
            {
                vector titem = vector(1,c0);
                (*pR)[c0].push_back(titem);
            }
        }
        
        for(int k = 1; k < num.size(); ++k)
        {
            int ck = num[k];
            for(int t = 1; t <= target; ++t)
            {
                (*pT)[t].clear();
                vector > &excludePre = (*pR)[t];
                for( int i = 0 ; i < excludePre.size(); ++i)
                {
                    (*pT)[t].push_back(excludePre[i]);
                }
                if(t - ck > 0)
                {
                    vector > &includePre = (*pR)[t - ck];
                    for( int i = 0 ; i < includePre.size(); ++i)
                    {
                        vector tResult = includePre[i];
                        tResult.push_back(ck);
                        (*pT)[t].push_back(tResult);
                    }
                } else if (t == ck)
                {
                    (*pT)[t].push_back(vector(1,ck));
                }
            }
            vector > > *temp = pR;
            pR = pT;
            pT = temp;
        }
        vector > &result = (*pR)[target];
        sort(result.begin(),result.end());
        result.erase(unique(result.begin(),result.end()),result.end());
        return result;
    }
};

2 thoughts on “LeetCode题目:Combination Sum II

  1. zp

    我也贴一个

    class Solution {
    public:
    vector<vector > combinationSum2(vector &num, int target) {
    sort(num.begin(), num.end());
    vector<vector<vector > > dp;
    for (int i = 0; i <= target; ++i) {
    vector<vector > empty;
    dp.push_back(empty);
    }
    for (int i = 0; i = 1; –k) {
    if (k – x == 0) {
    vector temp;
    temp.push_back(x);
    dp[k].push_back(temp);
    } else if ((k – x > 0) && (!dp[k – x].empty())) {
    for (int j = 0; j < dp[k – x].size(); ++j) {
    vector temp = dp[k – x][j];
    temp.push_back(x);
    dp[k].push_back(temp);
    }
    }
    }
    }
    vector<vector > result = dp[target];
    sort(result.begin(),result.end());
    result.erase(unique(result.begin(),result.end()),result.end());
    return result;

    }
    };

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注