Untitled

class Solution {
private:
    void dfs(int pos, int target, vector<int> &nums, pair<vector<int>, int> cur, vector<vector<int>> &ret) {
        if (pos >= nums.size()) return;

        if (cur.second > target) return;
        if (cur.second == target) {
            ret.push_back(cur.first);
        }
        
        //go right
        dfs(pos+1, target, nums, cur, ret);

        // take current and stay at pos
        cur.first.push_back(nums[pos]);
        cur.second = cur.second + nums[pos];
        dfs(pos, target, nums, cur, ret);
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ret;
        pair<vector<int>, int> tmp{{}, 0};

        dfs(0, target, candidates, tmp, ret);

        return ret;
    }
};