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

Diffculty
Medium

Similar Problems

[LeetCode 76] Minimum Window Substring Hard [LeetCode 325] Maximum Size Subarray Sum Equals k Medium

Analysis

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int target) { // k 个元素
        vector<vector<int>> ret;
        vector<int> v;
        combinationSum3(k, target, v, ret, 1);
        return ret;
    }

private:
    void combinationSum3(int k, int target, vector<int>& v, vector<vector<int>>& ret, int begin){
        if(k == 0 && target == 0){
            ret.push_back(v);
            return;
        }
        for(int i = begin; i < 10 && i <= target; i++){
            v.push_back(i);
            combinationSum3(k - 1, target - i, v, ret, i + 1);
            v.pop_back();
        }
    }

};

Solutions

class Solution {
public:
    std::vector<std::vector<int> > combinationSum3(int k, int n) {
        std::vector<std::vector<int> > res;
        std::vector<int> combination;
        combinationSum3(1, n, res, combination, k);
        return res;
    }
private:
    void combinationSum3(int begin, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int stillneed) {
        if (target == 0) {
            res.push_back(combination);
            return;
        }
        else if (stillneed == 0)
            return;

        // target >= i + (i+1) + ... + (i +need-1) = i * need + need * (need - 1) / 2;
        // You can also written as follows:
        // int end = (target - need * (need - 1) / 2) / need;
        // if (end > 9 - need + 1)
        //     return;
        // for (int i = begin; i <= end; ++i) {
        //     combination.push_back(i);
        //     combinationSum3(target - i, res, combination, i + 1, need - 1);
        //     combination.pop_back();
        // }

        for (int i = begin; i <= 9 && target >= i * need + need * (need - 1) / 2; ++i) {
            combination.push_back(i);
            combinationSum3(i + 1, target - i, res, combination, need - 1);
            combination.pop_back();
        }
    }
};

Reference