# Share my C++ solution,easy to understand

• ``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ret;
vector<int> temp;

if (k <= 0 || n <= 0)
return ret;

dfs(n, 1, k, temp, ret);

return ret;
}

void dfs(int target, int start, int k, vector<int> temp, vector<vector<int>> &ret)
{
if (target < start)
return;

int i = start, len = 0;
for (i = start; i <= 9; ++i)
{
temp.push_back(i);
len = temp.size();
if (target == i && len == k)
{
ret.push_back(temp);
return;
}
if (target > i && len < k)
dfs(target-i, i+1, k, temp, ret);

temp.pop_back();
}
}
};``````

• Compare it with another two similar problems:

"Combination Sum II":

``````class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> temp;
int n = candidates.size();

if (n == 0)
return ret;

sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, n, temp, ret);

return ret;
}

void dfs(vector<int>& candidates, int target, int start, int n, vector<int> temp, vector<vector<int>>& ret)
{
if (target < candidates[start])
return;

int i= start, j = 0;

while (i < n)
{
temp.push_back(candidates[i]);

if (target == candidates[i])
{
ret.push_back(temp);
return;
}
else if (target > candidates[i])
dfs(candidates, target-candidates[i], i+1, n, temp, ret);

temp.pop_back();

while (i+1 < n && candidates[i+1] == candidates[i])
++i;

++i;
}
}
};
``````

"Combination Sum":

``````class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> temp;
int n = candidates.size();
if (n == 0)
return ret;

sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, temp, ret);

return ret;
}

void dfs(vector<int>& candidates, int target, int start, vector<int> temp, vector<vector<int>> &ret)
{
int n = candidates.size(), i = 0;
if (target < candidates[start])
return;

for (i = start; i < n; i++)
{
temp.push_back(candidates[i]);

if (target == candidates[i])
{
ret.push_back(temp);
return;
}
else if (target > candidates[i])
dfs(candidates, target-candidates[i], i, temp, ret);

temp.pop_back();
}
}
};``````

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