leetcode39.组合总和（中等）

思路：类似多背包问题
难点：不熟悉模板

if (满足条件) {
	更新ans;
	return ;
}
if (index == n - 1 || 不满足条件) return ;
ans.push_back(a[m]);
dfs(m); 
ans.pop_back();
dfs(m+1);

易错点：
dfs(index + 1, sum + candidates[index + 1], ans, each, candidates, target); 第二个参数写错了，不选index的一个了，所以应该是当前层的sum ！！！

class Solution {
public:
    void dfs(int index, int sum, vector> &ans, vector &each, vector& candidates, int target);
    vector> combinationSum(vector& candidates, int target) {
        
        //多背包写法
        vector> ans;
        vector each;
        dfs(0, 0, ans, each, candidates, target);
        return ans;
    }
};
void Solution :: dfs(int index, int sum, vector> &ans, vector &each, vector& candidates, int target) {
    if (sum == target) {
        ans.push_back(each);
        return ;
    }
    if (index == candidates.size() || sum > target) return ;
    each.push_back(candidates[index]);
    dfs(index, sum + candidates[index], ans, each, candidates, target);
    each.pop_back();
    //dfs(index + 1, sum + candidates[index + 1], ans, each, candidates, target); 错误
    dfs(index + 1, sum, ans, each, candidates, target);
}