September LeetCoding Challenge, Day 12: Combination Sum III

September 13, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The 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:

class Solution {
  vector<vector<int>> ans;
  vector<int> next;

  void dfs(int curr_sum, int next_num, int n_nums, int k, int n) {
    if (n_nums == k) {
      if (curr_sum == n)
    for (int i = next_num; i <= 9; ++i) {
      if (curr_sum + i > n)
      dfs(curr_sum + i, i + 1, n_nums + 1, k, n);

  vector<vector<int>> combinationSum3(int k, int n) {
    dfs(0, 1, 0, k, n);
    return ans;