Combination Sum III

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.

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. [1,2,1] is not valid because 1 is used twice.

Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.

Example 5:

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

Constraints:

• 2 <= k <= 9

• 1 <= n <= 60

Solutions

🧠 Cpp

class Solution
{

    //size_t pick_next_free_position(char &bitmask, current)
public:
    vector<vector<int>> combinationSum3(int k, int n)
    {
        //input validation
        if(k > n)
            return {};

        vector<vector<int>> res;
        set<vector<int>> res_set;
        vector<int> holder(k, 1);
        //to mark current selected numbers

        size_t iter_max = std::min(9, (n > 3 ? n-k+1 : n));

        function<void(size_t, vector<int>)> increment_holder;
        //add vector of num to ignore to ignore
        increment_holder = [&](size_t pos, vector<int> to_ignore)
        {
            for(int i = 0; i <= iter_max; )
            {
                if(i == iter_max)
                {
                    holder[pos] = 1;
                    break;
                }

                if(pos==k-1)
                {
                    const int sum = std::accumulate(holder.begin(), holder.end(),0);
                    if(sum == n)
                    {
                        auto holder_copy = holder;
                        std::sort(holder_copy.begin(), holder_copy.end());
                        auto uq_end = std::unique(begin(holder_copy), end(holder_copy));
                        if(uq_end == end(holder_copy))
                            res_set.insert(std::move(holder_copy));
                    }
                    if(sum > n)
                    {
                        holder[pos] = 1;
                        break;
                    }
                }
                else
                {
                    to_ignore.push_back(holder[pos]);
                    increment_holder(pos+1, to_ignore);
                }
                do
                {
                    ++i, ++holder[pos];
                } while(std::count(begin(to_ignore), end(to_ignore),holder[pos]));

                if(i == iter_max)
                {
                    holder[pos] = 1;
                    break;
                }


            }
        };

        increment_holder(0, {});

        std::copy(res_set.begin(), res_set.end(), back_inserter(res));

        return res;
    }
};