> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/combination-sum-iii.md).

# Combination Sum III

## [Combination Sum III](https://leetcode.com/problems/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

```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;
    }
};
```