# Clean 0ms DFS and backtracking C++ solution

• This problem can be rephrased into the following, given an input array consists of numbers from 1 to 9, find its subset of size k which sums to sum n.

Naturally we can have a DFS solution to solve it with O(2^9). At each level indicated by the current value we need to pick or skip, we will branch into two cases: include this number or skip this number.

Thus the solution is very straightforward:

vector<vector<int>> combinationSum3(int k, int n) {
vector<int> path;
vector<vector<int>> result;
combinations(1, k, n, path, result);
return result;
}

void combinations(int current, int k, int n, vector<int>& path, vector<vector<int>>& result) {
if (path.size() == k) {
if (n == 0) result.push_back(path);
return;
}
if (current > 9) return;

/* do not add current */
combinations(current+1, k, n, path, result);

path.push_back(current);
combinations(current+1, k, n-current, path, result);
path.pop_back();
}

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