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();
    }
  }
};

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

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