39. Combination Sum

Problem from leetcode 39. Combination Sum

---

我们没有什么快捷的方式，只能 暴力枚举， 当然采用适当的branch and bound可以加快代码的运行。

---

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
        //sort first
        sort(candidates.begin(), candidates.end());
        
        vector<vector<int> > result;
        vector<int> cur;
        dfs(candidates, target, result, cur, 0, 0);
        return result;
    }
    void dfs(vector<int> &candidates, int target, vector<vector<int> > &result, vector<int> &cur, int curSum, int pos)
    {
        if(curSum == target)
        {
            result.push_back(cur);
            return;
        }
        int size = candidates.size();
        if(pos == size) return;
        if(curSum + candidates[pos] > target) return;
        //now may still have valid combinatioms
        //we can never add candidates[pos], 
        //or we can add one candidates[pos],
        //or we can add two candidates[pos], 
        //or we can add three candidates[pos]...              
        vector<int> tmp(cur);
        int tmpSum = curSum;
        while(tmpSum <= target)
        {
            dfs(candidates, target, result, tmp, tmpSum, pos+1);
            tmp.push_back(candidates[pos]);
            tmpSum += candidates[pos];
        }
    }
};

还有一种暴力枚举的写法:

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
        //sort first
        sort(candidates.begin(), candidates.end());
        
        vector<vector<int> > result;
        vector<int> cur;
        dfs(candidates, target, result, cur, 0, 0);
        return result;
    }
    void dfs(vector<int> &candidates, int target, vector<vector<int> > &result, vector<int> &cur, int curSum, int pos)
    {
        if(curSum == target)
        {
            result.push_back(cur);
            return;
        }
        int size = candidates.size();
        if(pos == size) return;
        if(curSum + candidates[pos] > target) return;
        for(int i = pos; i < size; ++i)
        {
            curSum += candidates[i];
            cur.push_back(candidates[i]);
            dfs(candidates, target, result, cur, curSum, i);
            cur.pop_back();
            curSum -= candidates[i];
        }
    }
};

第一个版本 44ms, 第二个版本 12ms.
当然我们也可以写iterative的代码：

class Solution {
public:
    struct Entry{
        vector<int> cur;
        int curSum;
        int pos;
        Entry(){
            curSum = 0;
            pos = 0;
        }
        //no need to write copy constructor since
        //synthesized one is enough for use
    };
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //sort first
        sort(candidates.begin(), candidates.end());
        int size = candidates.size();
        
        vector<vector<int>> result;
        queue<Entry> tool;
        Entry first;
        tool.push(first);
        while(!tool.empty())
        {
            Entry tmp = tool.front(); tool.pop();
            if(tmp.curSum == target)
            {
                result.push_back(tmp.cur);
                continue;
            }
            if(tmp.curSum > target || tmp.pos >= size || tmp.curSum+candidates[tmp.pos] > target) continue;
            while(tmp.curSum <= target)
            {
                Entry t(tmp); t.pos = tmp.pos+1;
                tool.push(t);
                tmp.cur.push_back(candidates[tmp.pos]);
                tmp.curSum += candidates[tmp.pos];
            }
        }
        
        return result;
    }
};