Combination Sum - I, II, III and IV using Recursion
Goldie
108
Recursion

Here is my Solution using recursion for all 4 of the Combination Sum Problems.

For Combination Sum , It is a simple variation of sum of subsets problem.

Code -:

Combination Sum I

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int count = 0;
        int sum = 0;
        vector<int> s;
        vector<vector<int>> ans;
        summation(candidates, 0, sum, target, count, s, ans);
        return ans;
    }
    
    void summation(vector<int>& nums, int i, int& sum, int& target, int& count, vector<int>& s, vector<vector<int>>& ans) {
        for (int j = i; j < nums.size(); j++) {
            sum += nums[j];
            s.push_back(nums[j]);
            if (sum < target) {
                summation(nums, j, sum, target, count, s, ans);
            }
            else if (sum == target) {
                ans.push_back(s);
                count++;
            }
            sum -= nums[j];
            s.pop_back();
        }
    }

Beats 90% of the submissions

Combination Sum II

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        int count = 0;
        int sum = 0;
        vector<int> s;
        vector<vector<int>> ans;
        sort(candidates.begin(),candidates.end());
        for(int i = 0;i < candidates.size();i++) {
            sum += candidates[i];
            s.push_back(candidates[i]);
            if(sum < target) {
                summation(candidates,i,sum,target,count,s,ans);
            }
            else if(sum == target) {
                ans.push_back(s);
            }
            s.pop_back();
            sum -= candidates[i];
            int j = i;
            while(j < candidates.size() && candidates[j] == candidates[i]) {
                j++;
            }
            i = j - 1;
        }
        return ans;
    }
    
    void summation(vector<int>& nums, int i, int& sum, int& target, int& count, vector<int>& s, vector<vector<int>>& ans) {
        for (int j = i + 1; j < nums.size(); j++) {
            sum += nums[j];
            s.push_back(nums[j]);
            if (sum < target) {
                summation(nums, j, sum, target, count, s, ans);
            }
            else if (sum == target) {
                ans.push_back(s);
                count++;
            }
            sum -= nums[j];
            s.pop_back();
            int k = j;
            while(k < nums.size() && nums[j] == nums[k]) k++;
            j = k - 1;
        }
    }

Beats 50% of the submissions

Combination Sum III

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums = { 1,2,3,4,5,6,7,8,9 };
        int target = n;
        int sum = 0;
        int count = 0;
        vector<int> s;
        vector<vector<int>> ans;
        for(int i = 0;i < 9;i++) {
            sum += nums[i];
            s.push_back(nums[i]);
            count++;
            if(count > k || sum > target){
                count--;
                s.pop_back();
                sum -= nums[i];
                break;
            }
            if(sum < target) {
                summation(nums,i,count,sum,target,k,s,ans);
            }
            else if(count == k && sum == target) {
                ans.push_back(s);
            }
            count--;
            s.pop_back();
            sum -= nums[i];
        }
        return ans;
    }
    
    void summation(vector<int>& nums,int i,int& count,int& sum,int& target,int& k,vector<int>& s,vector<vector<int>>& ans) {
        for(int j = i + 1;j < 9;j++) {
            sum += nums[j];
            s.push_back(nums[j]);
            count++;
            if(count > k || sum > target){
                count--;
                s.pop_back();
                sum -= nums[j];
                break;
            }
            if(sum < target) {
                summation(nums,j,count,sum,target,k,s,ans);
            }
            else if(count == k && sum == target) {
                ans.push_back(s);
            }
            count--;
            s.pop_back();
            sum -= nums[j];
        }
    }

Beats 50% of the submissions

Combination Sum IV

int combinationSum4(vector<int>& nums, int target) {
    int count = 0;
    int sum = 0;
    summation(nums,0,sum,target,count);
    return count;
}

void summation(vector<int>& nums, int i, int& sum, int& target, int& count) {
    for(int j = 0;j < nums.size();j++) {
        sum += nums[j];
        if(sum < target) {
            summation(nums,j,sum,target,count);
        }
        else if(sum == target) {
            count++;
        }
        sum -= nums[j];
    }
}

Gives TLE.

Comments (0)