39. 组合总和

Introduction

Question：39. 组合总和

Analysis

• 解空间：一个长度与candidates一致的数组ans[n]，ans[i]表示candidates[i]在解中的个数。
• 剪枝条件：$\sum{ candidates[i]*ans[i] } \le target$

Implement

vector<vector<int>> res;
vector<int> ans;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    ans = vector<int>(candidates.size(), 0);
    func(candidates, target, 0);
    return res;
}
void func(vector<int>& candidates, int target, int index) {
    if (target == 0) {
        // generator ans
        vector<int> vec;
        for(int i = 0;i <candidates.size(); i++) {
            for(int c = ans[i], v = candidates[i];c > 0;c--) {
                vec.push_back(v);
            }
        }
        res.push_back(vec);
        return;
    }
    if (index == candidates.size()) return ;
    for(int c = 0;c * candidates[index] <= target; c++) {
        ans[index] = c;
        func(candidates, target - c*candidates[index], index + 1);
    }
    ans[index] = 0;
}