Leetcode - Combination / Combination sum 1/2/3

1. Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

In this kind problem, we will need to go through from 1 to n in increasing order.

We need to apply the Backtracking method here to solve this problem. Backtraking

And the Depth First Search style algorithm can be applied to the scenario give all the possible

solutions to the problem.

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> ret;
        if(n <= 0) //corner case invalid check
            return ret;

        vector<int> curr;
        DFS(ret,curr, n, k, 1); //we pass ret as reference at here
        return ret;
    }

    void DFS(vector<vector<int>>& ret, vector<int> curr, int n, int k, int level)
    {
        if(curr.size() == k)
        {
            ret.push_back(curr);
            return;
        }
        if(curr.size() > k)  // consider this check to save run time
            return;

        for(int i = level; i <= n; ++i)
        {
            curr.push_back(i);
            DFS(ret,curr,n,k,i+1);
            curr.pop_back();
        }
    }

};

2. Combination sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is: 

[
  [7],
  [2, 2, 3]
]

In this case, we apply DFS and backtracking to solve this problem. Noted that we will sort the

candidates first and during the loop we will skip to the last element of same values.

class Solution { public: vector<vector<int> > combinationSum(vector<int> &candidates, int target) { vector<vector<int> > allSol; vector<int> sol; if(candidates.empty()) return allSol; sort(candidates.begin(),candidates.end()); findCombSum(candidates, 0, target, sol, allSol); return allSol; } void findCombSum(vector<int> &candidates, int start, int target, vector<int> &sol, vector<vector<int>> &allSol) { if(target==0) { allSol.push_back(sol); return; } for(int i=start; i<candidates.size(); i++) { if(i>start && candidates[i]==candidates[i-1]) continue; if(candidates[i]<=target) { sol.push_back(candidates[i]); findCombSum(candidates, i, target-candidates[i], sol, allSol); sol.pop_back(); } if(candidates[i]>target) return; //This can save the runtime } } };

3. Combination sum 2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Comparing to combination sum 1, the answer can't contain duplicate numbers.

All we need to do is increment the the i- value to accomplish this part.

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > allSol;
        if(num.empty()) return allSol;
        sort(num.begin(),num.end());
        vector<int> sol;
        findCombSum2(num, 0, target, sol, allSol);
        return allSol;
    }
    
    void findCombSum2(vector<int> &num, int start, int target, vector<int> &sol, vector<vector<int> > &allSol) {
        if(target==0) {
            allSol.push_back(sol);
            return;
        }
        
        for(int i=start; i<num.size(); i++) {
            if(i>start && num[i]==num[i-1]) continue;
            if(num[i]<=target) {
                sol.push_back(num[i]);
                findCombSum2(num, i+1, target-num[i], sol, allSol);
                sol.pop_back();
            }
        }
    }
};

4. Combination sum 3

.Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};