LeetCode题目:Combination Sum,动态规划

By | 2012 年 9 月 15 日

这道题是动态规划,先写一个伪代码是挺好的方法。可以先笼统的写出来算法,算法ok了再注意语法之类的细节。


题目描述如下:
Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
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 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]



小集合12ms,大集合1416ms过

class Solution {
public:
    vector > combinationSum(vector &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (candidates.size() == 0)
            return vector >();
        sort(candidates.begin(),candidates.end());
        vector > > *pR = new vector > >(target + 1);
        vector > > *pT = new vector > >(target + 1);
        for (int t = 1; t <= target; ++ t)
        {
            int c = candidates[0];
            if (t % c == 0)
            {
                (*pR)[t].push_back(vector(t/c,c));
            }
        }
        for (int k = 1; k < candidates.size(); ++k)
        {
            int ck = candidates[k];
            for (int t = 1 ; t <= target; ++t)
            {
                (*pT)[t].clear();
                for (int p = 0; p * ck <= t; ++p)
                {
                    int remain = t - ck * p;
                    if (remain == 0)
                    {
                        (*pT)[t].push_back(vector(p,ck));
                    }
                    else
                    {
                        vector > &rRemain = (*pR)[remain];
                        for (int irr = 0; irr < rRemain.size() ;++ irr)
                        {
                            vector newSum(rRemain[irr]);
                            for(int ip = 0; ip < p; ++ip)
                                newSum.push_back(ck);
                            (*pT)[t].push_back(newSum);
                        }
                    }
                }
            }
            vector > > *pTemp = pR;
            pR = pT;
            pT = pTemp;
        }
        return (*pR)[target];
    }
};

21 thoughts on “LeetCode题目:Combination Sum,动态规划

  1. traveller

    你的方法属于DP嘛?DP最基本的要求是最优子结构,但是这个问题好像没有最优化化问题吧

    Reply
    1. uniEagle Post author

      我是将问题转变成了“哪些可能的组合可以得到和sum?”来解决。这是一个系列问题,sum从1到target。在解决比如sum=k的时候,需要去计算sum=1到k-1的情况,这就是子问题。
      DP的要求是降低子问题的重复计算,在我的这段代码里,我将这些子问题的计算结果都存放在数组里,所以每一个子问题,实际上只需要计算一次。通过这样的方法来提高速度。

      Reply
      1. traveller

        恩,我明白你是通过N问题降低为1~N-1的子情况。
        但是这好像并不是一个最优问题,好像应该算模仿DP的子结构思想而已,不过我对DP研究也不深入~仅作讨论~

        Reply
        1. uniEagle Post author

          恩,我理解的DP是这样的:在计算最终solution的时候,需要计算一堆子问题,而有些子问题需要计算很多次。如果将这些子问题的结果存储起来,在后续问题的计算中只需要查询,就可以避免这些子问题的重复计算。
          我理解中,这就是DP。当然在最优化问题中比较容易引入这种方法。

          Reply
        2. uniEagle Post author

          恩,能解决问题就行,这种方法最能体现“用空间换时间”。而且有时候遇到一些问题,没什么思路,这种把问题分成子问题的思想倒是提供了一个不错的思考路径。

          Reply
  2. schou

    i don’t quite understand why this is a DP problem. My Java code could pass large judge around 700ms.

    public class Solution {
    public ArrayList<ArrayList> combinationSum(int[] candidates, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    if(candidates == null || candidates.length == 0)
    return result;

    Arrays.sort(candidates);
    if(candidates[0] > target)
    return result;

    ArrayList one = new ArrayList();
    find(candidates, 0, candidates.length, target, result, one);
    return result;
    }

    private void find(int[] candidates, int start, int end, int target, ArrayList<ArrayList> result, ArrayList one) {
    if(target == 0) {
    result.add(new ArrayList(one));
    return;
    }

    for(int i = start; i < end; i++) {
    if(target < candidates[i])
    continue;

    one.add(candidates[i]);
    target -= candidates[i];

    find(candidates, i, end, target, result, one);
    target += one.remove(one.size()-1);
    }
    }
    }

    Reply
    1. traveller

      我最一开始也用的递归做(c++),但是处理不要引用就会出现内存溢出的错误。

      Reply
        1. traveller

          恩~能写成迭代还是迭代好。之前看到你很多地方都写了迭代,很犀利的说~

          Reply
          1. uniEagle Post author

            是,我倾向于写成迭代,主要就是为了避免系统分配下来的栈溢出。不过递归的解法写出来都通常比迭代解法更简洁,思路更清晰,更容易读懂。

    2. uniEagle Post author

      Ah, your algorithm is simpler than mine.
      I turned this problem in a DP problem by solving the set of sub-problem of “What combinations will add up to ‘sum’? “, while the sum from 1 to target.
      The point is that, when we know “what combinations will add up to a sum from 1 to k-1”, we can easily calculate “what combinations will add up to a sum of k”, and avoid a lot of sub-problem calculation with looking up the vector than stored the previous calculation result.
      However, the algorithm can be speeded up by carefully choose the step of sum increasing. Some input, we can select a much higher value than 1.

      Reply
    1. uniEagle Post author

      Yes, DFS will be faster than my algorithm, because of the step selection. In my code, that is 1, but for most input, a much higher value is applicable, and will speed up the calculation.

      Reply
  3. lzj


    public ArrayList<ArrayList> combinationSum(int[] candidates, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
    Arrays.sort(candidates);

    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    int len = candidates.length;
    if (len == 0 || candidates[0] > target) {
    return result;
    }
    ArrayList current = new ArrayList();
    for (int i = 0; i < len && candidates[i] 0 && candidates[i] == candidates[i - 1]) {
    continue;
    }
    work(candidates, i, target, current, result);
    }
    return result;
    }

    private void work(int[] candidates, int start, int target, ArrayList current,
    ArrayList<ArrayList> result) {
    int size = current.size();
    int len = candidates.length;
    for (int i = 1; i * candidates[start] <= target; ++i) {
    current.add(candidates[start]);
    int inc = i * candidates[start];
    int removePos = current.size();
    if (target - i * candidates[start] == 0) {
    result.add(deepCopy(current));
    break;
    } else {
    int next = start + 1;
    while (next < len && candidates[start] == candidates[next]) {
    ++next;
    }
    while (next < len && candidates[next] <= target - inc) {
    work(candidates, next, target - inc, current, result);
    ++next;
    removeFrom(current, removePos);
    }
    }
    }
    removeFrom(current, size);
    }

    private void removeFrom(ArrayList a, int start) {
    int size = a.size();
    for (int i = size - 1; i >= start; --i) {
    a.remove(i);
    }
    }

    private ArrayList deepCopy(ArrayList src) {
    int size = src.size();
    ArrayList result = new ArrayList();
    for (int i = 0; i < size; ++i) {
    result.add(src.get(i));
    }
    return result;
    }

    Reply
  4. lzj

    这个你的解法有问题, 如果Target 比较大,你会超时。

    在Target值没有限定的情况下需要用搜索+剪枝的方法。

    我的解法(700ms large Java):
    public ArrayList<ArrayList> combinationSum(int[] candidates, int target) {
    // Start typing your Java solution below
    // DO NOT write main() function
    Arrays.sort(candidates);

    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    int len = candidates.length;
    if (len == 0 || candidates[0] > target) {
    return result;
    }
    ArrayList current = new ArrayList();
    for (int i = 0; i < len && candidates[i] 0 && candidates[i] == candidates[i – 1]) {
    continue;
    }
    work(candidates, i, target, current, result);
    }
    return result;
    }

    private void work(int[] candidates, int start, int target, ArrayList current,
    ArrayList<ArrayList> result) {
    int size = current.size();
    int len = candidates.length;
    for (int i = 1; i * candidates[start] <= target; ++i) {
    current.add(candidates[start]);
    int inc = i * candidates[start];
    int removePos = current.size();
    if (target – i * candidates[start] == 0) {
    result.add(deepCopy(current));
    break;
    } else {
    int next = start + 1;
    while (next < len && candidates[start] == candidates[next]) {
    ++next;
    }
    while (next < len && candidates[next] <= target – inc) {
    work(candidates, next, target – inc, current, result);
    ++next;
    removeFrom(current, removePos);
    }
    }
    }
    removeFrom(current, size);
    }

    private void removeFrom(ArrayList a, int start) {
    int size = a.size();
    for (int i = size – 1; i >= start; –i) {
    a.remove(i);
    }
    }

    private ArrayList deepCopy(ArrayList src) {
    int size = src.size();
    ArrayList result = new ArrayList();
    for (int i = 0; i < size; ++i) {
    result.add(src.get(i));
    }
    return result;
    }

    Reply
  5. Pingback: LeetCode题目:Combination Sum II - uniEagle

发表评论

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