# C++, 0ms: Backtracking, Clean Code

• C++, 0ms: Backtracking

``````vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;

bt_solution(result, answer, k, n, 1); // Start from digit 1

return result;
}

void bt_solution(vector<vector<int>>& r, vector<int>& a, int k, int n, int digit) {
if(k == 0) {
if(n == 0) r.push_back(a);
return;
}

for(int i = digit; i < 10; ++i) {
a.push_back(i);
bt_solution(r, a, k-1, n-i, i+1);
a.pop_back();
}
}
``````

• Good solution.

``````if(k == 0){
if(n == 0) r.push_back(a);
return;
}
``````

can be optimized to

``````if (k == 0 || n <= 0) {
if (k == 0 && n == 0) r.push_back(a);
return;
}
``````

• @fei26

Right. I was assuming that the input n will always be larger than 0.
Consider the input n might be <= 0, we could early out before we even run the solution function.

``````vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;

if(n <= 0) { // If n is less and equal to 0, there is no answer.
}

return result;
}

void bt_solution(vector<vector<int>>& r, vector<int>& a, int k, int n, int start) {
if(k == 0) {
if(n == 0) r.push_back(a);
return;
}

for(int i = start; i < 10; ++i) {
a.push_back(i);
bt_solution(r, a, k-1, n-i, i+1);
a.pop_back();
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.