Combination Sum III LeetCode Solution | Easy Approach

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.
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

Combination Sum III Solutions

✅Time: OO(C(9,k))=O(9k)
✅Space: O(n)

C++

class Solution {
 public:
  vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> ans;
    dfs(k, n, 1, {}, ans);
    return ans;
  }

 private:
  void dfs(int k, int n, int s, vector<int>&& path, vector<vector<int>>& ans) {
    if (k == 0 && n == 0) {
      ans.push_back(path);
      return;
    }
    if (k == 0 || n <= 0)
      return;

    for (int i = s; i <= 9; ++i) {
      path.push_back(i);
      dfs(k - 1, n - i, i + 1, move(path), ans);
      path.pop_back();
    }
  }
};

Java

 
class Solution {
  public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(k, n, 1, new ArrayList<>(), ans);
    return ans;
  }

  private void dfs(int k, int n, int s, List<Integer> path, List<List<Integer>> ans) {
    if (k == 0 && n == 0) {
      ans.add(new ArrayList<>(path));
      return;
    }
    if (k == 0 || n < 0)
      return;

    for (int i = s; i <= 9; ++i) {
      path.add(i);
      dfs(k - 1, n - i, i + 1, path, ans);
      path.remove(path.size() - 1);
    }
  }
}

Python

  class Solution:
  def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    ans = []

    def dfs(k: int, n: int, s: int, path: List[int]) -> None:
      if k == 0 and n == 0:
        ans.append(path)
        return
      if k == 0 or n < 0:
        return

      for i in range(s, 10):
        dfs(k - 1, n - i, i + 1, path + [i])

    dfs(k, n, 1, [])
    return ans

Watch Tutorial

Checkout more Solutions here