Combination Sum 1

Provided with a goal integer target and an array of unique integer candidates, provide a list of all possible combinations of candidates in which the selected numbers add up to the target. The combinations can be returned in any order.

A candidate may be selected from the pool an infinite number of times. There are two distinct combinations if the frequency if at least one of the selected figures differs.

 Example :
// Input : candidates = [2, 3, 5, 4] , target = 7

// Output : [ [2, 2, 3] , [3, 4] , [5, 2] ]

void func(int ind,vector<vector<int>>&ans,vector<int>&temp,vector<int>&candidates,int sum){
        if(sum==0){
            ans.push_back(temp);
            return;
        }
        if(sum<0) return;
        if(ind==candidates.size()) return;
        func(ind+1,ans,temp,candidates,sum);
        temp.push_back(candidates[ind]);
        func(ind,ans,temp,candidates,sum-candidates[ind]);
        temp.pop_back();

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) { 
        vector<vector<int>>ans;
        vector<int>temp;
        func(0,ans,temp,candidates,target);
        return ans;
    }

Combination Sum 2

Given collection of candidate numbers (candidates) and a integer target.Find all unique combinations in candidates where the sum is equal to the target.There can only be one usage of each number in the candidates combination and return the answer in sorted order.

e.g : The combination [1, 1, 2] and [1, 2, 1] are not unique.

Example 
// Input : candidates = [2, 1, 2, 7, 6, 1, 5] , target = 8
// Output : [ [1, 1, 6] , [1, 2, 5] , [1, 7] , [2, 6] ]

void func(int ind, vector<vector<int>> &ans, vector<int> &temp, vector<int> &candidates, int sum)
    {
        if (sum == 0)
        {
            ans.push_back(temp);
            return;
        }
        if (sum < 0)
            return;
        if (ind == candidates.size())
            return;
        temp.push_back(candidates[ind]);
        func(ind + 1, ans, temp, candidates, sum - candidates[ind]);
        temp.pop_back();

        for (int i = ind + 1; i < candidates.size(); i++)
        {
            if (candidates[i] != candidates[ind])
            {
                func(i, ans, temp, candidates, sum);
                break;
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        vector<int> temp;
        func(0, ans, temp, candidates, target);
        return ans;
    }

Combination Sum 3

Determine all possible set of k numbers that can be added together to equal n while meeting the following requirements:

1. There is only use of numerals 1 through 9.
2. A single use is made of each number.

Return list of every feasible combination that is allowed. The combinations can be returned in any order, but the list cannot have the same combination twice.

Examples
// Input : k = 3 , n = 7
// Output : [ [1, 2, 4] ]

    void func(int sum, int k, int i, vector<vector<int>> &ans, vector<int> &temp)
    {
        if (sum == 0 && temp.size() == k) //maintain k size window
        {
            ans.push_back(temp);
            return;
        }
        if (sum <= 0 || temp.size() > k) //maintain k size window
            return;

        for (int j = i; j <= 9; j++) 
        {
            if (j <= sum) // check if j can be part of the combination
            {
                temp.push_back(j); // add j to the current combination
                func(sum - j, k, j + 1, ans, temp); // move to the next number
                temp.pop_back(); // backtrack to explore other combinations (branching)
            }
            else
                break;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n)
    {
        vector<vector<int>> ans;
        vector<int> temp;
        func(n, k, 1, ans, temp);
        return ans;
    }