# September LeetCoding Challenge, Day 12: Combination Sum III

September 13, 2020The problem for September 12 is Combination Sum III. We are interested in finding all possible distinct 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. Since you can only use numbers from \(1\) to \(9\), both \(k\) and \(n\) can’t be negative; \(k\) is at most \(9\) and \(n\) is at most \(\sum_{i=1}^{9} i = \frac{9 \times (9 + 1)}{2} = 45\).

An exhaustive search using a DFS is possible given these limits, so it looks like a good candidate for a solution. The following is an implementation of that: