Leetocde 39: 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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• 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]

这一题是combination of coins的变形，实质两题是一个题目，利用DFS对每个值进行处理，DFS树共有N层，每一层可以有Target/num[cur]个分支。DFS的时间复杂度是O（2^n），空间复杂度是O（n）
注意： combination of coinsDFS遍历的时候由于每一个值可以使用多次，solution set里面存的是每个值使用的次数，而不是最后的solution。 最后需要进行处理。
class Solution {
private:
    void DFS(vector<int> candidates, int target, int cur, vector<int> solu, vector<vector<int>> &rst) {
        //base case
        if (target == 0) {
            rst.push_back(solu);
            return;
        }
        //out of coins
        if (cur == candidates.size()  || target < 0) return;
        for (int i = 0; i <= target / candidates[cur] ; i++) {
            solu.push_back(i);
            DFS(candidates, target- i*candidates[cur], cur+1, solu, rst);
            solu.pop_back();
        }
    }
public:
//DFS: combination of coins
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> rst;
        vector<vector<int>> buf;
        vector<int> solu;
        sort(candidates.begin(), candidates.end());
        //sanity check
        if (candidates.size() == 0) return rst;
        DFS(candidates, target, 0, solu, buf);
        for (int i = 0; i < buf.size(); i++) {
            vector<int> tmp;
            for (int j = 0; j < buf[i].size(); j++) {
                int count = buf[i][j];
                for (int k = 0; k < count; k++) {
                    tmp.push_back(candidates[j]);
                }
            }
            rst.push_back(tmp);
        }
        return rst;
    }
};