Combination Sum

PHOTO EMBED

Wed Jun 07 2023 12:15:56 GMT+0000 (Coordinated Universal Time)

Saved by @samarth_333 #c++

class Solution {
  public:
    //Function to return a list of indexes denoting the required 
    //combinations whose sum is equal to given number.
    void solve(int indx, int target, vector<int> &A, vector<vector<int>> &ans, vector<int> ds){
        if(target==0){ 
    		ans.push_back(ds);
    		return;
    	}
    	//returning if conditions are out of bound.
    	if(target<0 || indx>=A.size()) 
    		return;
        
        ds.push_back(A[indx]);
        solve(indx, target-A[indx], A, ans, ds);
        ds.pop_back();
        solve(indx+1, target, A, ans, ds);
    }
    
    vector<vector<int> > combinationSum(vector<int> &A, int B) {
        // Your code here
        vector<int> ds;
        vector<vector<int>> ans;
        sort(A.begin(), A.end());
        solve(0, B, A, ans, ds);
    }
};
content_copyCOPY

Created a recursive function solve(), which checks all combinations till the sum is less than the target sum and stores the required pair for which sum==target sum.

https://practice.geeksforgeeks.org/problems/combination-sum-1587115620/1