216

216. Combination Sum III (Medium)

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.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

Related Topics:
Array, Backtracking

Similar Questions:

• Combination Sum (Medium)

Solution 1. Backtracking

// OJ: https://leetcode.com/problems/combination-sum-iii
// Author: github.com/lzl124631x
// Time: O(2^9 * 9)
// Space: O(9)
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> tmp;
        function<void(int, int)> dfs = [&](int i, int n) {
            if (tmp.size() == k) {
                if (n == 0) ans.push_back(tmp);
                return;
            }
            if (i > 9) return;
            dfs(i + 1, n); // skip i
            tmp.push_back(i);
            dfs(i + 1, n - i); // use i
            tmp.pop_back();
        };
        dfs(1, n);
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/combination-sum-iii/
// Author: github.com/lzl124631x
// Time: O(2^9 * 9)
// Space: O(9)
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> tmp;
        function<void(int, int)> dfs = [&](int start, int n) {
            if (tmp.size() == k) {
                if (n == 0) ans.push_back(tmp);
                return;
            }
            for (int i = start; i <= min(9, n); ++i) {
                tmp.push_back(i);
                dfs(i + 1, n - i);
                tmp.pop_back();
            }
        };
        dfs(1, n);
        return ans;
    }
};

Solution 2. Bitmask Subset Traversal

// OJ: https://leetcode.com/problems/combination-sum-iii/
// Author: github.com/lzl124631x
// Time: O(2^9 * 9)
// Space: O(9)
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        for (unsigned m = 1; m < 1 << 9; ++m) {
            if (__builtin_popcount(m) != k) continue;
            vector<int> tmp;
            int sum = 0;
            for (int i = 1; i <= 9; ++i) {
                if (m >> (i - 1) & 1) {
                    sum += i;
                    tmp.push_back(i);
                }
            }
            if (sum == n) ans.push_back(tmp);
        }
        return ans;
    }
};

We can use Gosper's Hack to generate bitmasks with k bit 1's.

// OJ: https://leetcode.com/problems/combination-sum-iii/
// Author: github.com/lzl124631x
// Time: O(C(9, k) * 9)
// Space: O(9)
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        int m = (1 << k) - 1;
        while (m < (1 << 9)) {
            vector<int> tmp;
            int sum = 0;
            for (int i = 1; i <= 9; ++i) {
                if (m >> (i - 1) & 1) {
                    sum += i;
                    tmp.push_back(i);
                }
            }
            if (sum == n) ans.push_back(tmp);
            int c = m & -m, r = m + c;
            m = (((r ^ m) >> 2) / c) | r;
        }
        return ans;
    }
};