(15) Recursion: Combination Sum

Question Link and Solution Link

Difficulty: Medium

Problem Statement: Given an array of elements and a target sum you need to select elements from that array such that the sum of that elements are equal to the target element. Also, you can pick an element any number of times.

Approach: Every time we check whether the current element is less than the target sum or not. If it's less than the target sum then we will include that in a temporary vector and not change the index because in the future we might need to include that element and decrease the target sum value by that number.

Else what we can do is that to not include the number and in this case, we increment the index. The most important part is to pop_bcak() from the temporary vector. Also when our current index is equal to the size of the array and tar=0 then this means we achieve our sum and hence we will include it in our resultant vector.

void solve(int idx, vector<int> nums, int tar, vector<vector<int>> &res, vector<int> tmp) {
    if(idx==nums.size())
    {
        if(tar==0) res.push_back(tmp);
        return;
    }
    if(nums[idx] <= tar)
    {
        tmp.push_back(nums[idx]);
        solve(idx, nums, tar-nums[idx], res, tmp);
        tmp.pop_back();
    }
    solve(idx+1, nums, tar, res, tmp);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> tmp;
    solve(0, candidates, target, res, tmp);
    return res;
}

Subscribe to the newsletter so that you never miss any post or update just like this one.

You can follow me on Hashnode for:

• Daily Data Structure and Algorithm based questions

• Getting knowledge of various development-related tools, concepts, and practices

  Twitter , GitHub , LinkedIn and Hashnode