216 Combination Sum III

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]]

Example 2:

Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]

• Very icky, brute force approach of finding all the valid combinations and testing them.

vector<int> people;
vector<int> combination;
vector<vector<int>> final_combs;

void pretty_print(const vector<int>& v) {
    final_combs.push_back(v);
    //static int count = 0;
    //cout << "combination no " << (++count) << ": [ ";
    //for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
    //cout << "] " << endl;
    //pause();
}

void go(int offset, int k) {
    if (k == 0) {
        pretty_print(combination);
        return;
    }
    for (int i = offset; i <= people.size() - k; ++i) {
        combination.push_back(people[i]);
        go(i + 1, k - 1);
        combination.pop_back();
    }
}



vector<vector<int>> combinationSum3(int k, int n) {
    for (int i = 1; i <= 9; i++) { people.push_back(i); }
    go(0, k);
    vector<vector<int>> comb3;


    // check if == sum
    for (auto i : final_combs) {
        int sum = accumulate(i.begin(), i.end(), 0);
        if (sum == n) {
            comb3.push_back(i);
        }
    }

    return comb3;
}