combination_sum.txt

216. Combination Sum III
/*
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations.
The list must not contain the same combination twice, and the combinations may be returned in any order.
*\

class Solution {
public:
    void solve(int i, int k, int n, vector<vector<int>> &ans, vector<int> &temp){
        if(k == 0 && n == 0){
            ans.push_back(temp);
            return;
        }
        if(k < 0 || n < 0){
            return;
        }
        if(i > 9){
        return;
        }
        temp.push_back(i);
        solve(i+1, k-1, n-i, ans, temp);
        temp.pop_back();
        solve(i+1, k, n, ans, temp);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> temp;
        solve(1,k,n,ans,temp);
        return ans;
    }
};