Leetcode-216-combination-3

216-ac.cpp

// 216. Combination Sum III
// https://leetcode.com/problems/combination-sum-iii/
class Solution {
public:

    void backtrack(vector<int>& path, int next, int k, int n, vector<vector<int>>& combinations) {

        if (path.size() == k) {

            int sum = 0;
            for (int i : path) {
                sum += i;
            }

            if (sum == n) {
                combinations.push_back(path);
            }
        }

        for (int i = next; i <= 9; ++i) {

            path.push_back(i);
            backtrack(path, i + 1, k, n, combinations);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {

        vector<vector<int>> combinations;

        // pick k numbers
        // the sum is n

        for (int i = 1; i <= (9 - k + 1); ++i) {

            vector<int> path;

            path.push_back(i);
            backtrack(path, i + 1, k, n, combinations);
            path.pop_back();
        }
        return combinations;
    }
};

216-stackoverflow.cpp

// 216. Combination Sum III
// https://leetcode.com/problems/combination-sum-iii/
class Solution {
public:
    
    void backtrack(vector<int>& path, int next, int k, int n, vector<vector<int>>& combinations) {
        
        if (path.size() == k) {
            
            int sum = 0;
            for (int i : path) {
                sum += i;
            }
            
            if (sum == n) {
                combinations.push_back(path);
            }
        }

        for (int i = next; i <= (9 - k + path.size() + 1); ++i) {
            
            path.push_back(i);
            backtrack(path, i + 1, k, n, combinations);
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        
        vector<vector<int>> combinations;
        
        // pick k numbers
        // the sum is n
        
        for (int i = 1; i <= (9 - k + 1); ++i) {
            
            vector<int> path;
            
            path.push_back(i);
            backtrack(path, i + 1, k, n, combinations);
            path.pop_back();
        }
        return combinations;
    }
};