1、思路

每次DFS有两种选择：

• 将当前数字添加到组合中，且下一步可能再次选择同一个数字；

• 跳过当前数字，什么都不做。

2、代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> tmp;

public:
    void dfs(vector<int>& candidates, int i, int target)
    {
        if (target == 0)
        {
            res.push_back(tmp);
        }
        else if (target > 0 && i < candidates.size())
        {            
            tmp.push_back(candidates[i]);
            dfs(candidates, i, target - candidates[i]); //重复选当前元素
            tmp.pop_back();
            dfs(candidates, i + 1, target);             //不选当前元素
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, 0, target);

        return res;
    }
};