# This is my non-recursive DFS c++ code(28ms). Can anyone show me a shorter one?

• ``````class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
if (candidates.empty())
return res;
sort(candidates.begin(), candidates.end());
int canSize = candidates.size();
for (int i = 0; i < canSize; i++) {
stack<int> sta;
sta.push(candidates[i]);
int sum = 0, n = 0;
vector<int> tmpVec;
while (!sta.empty()) {
int curNum = sta.top();
sta.pop();
sum += curNum;
tmpVec.push_back(curNum);
n++;
if (sum >= target) {
if (sum == target)
res.push_back(tmpVec);
//弹出tmpVec的最后一个数
n--;
tmpVec.pop_back();
sum -= curNum;
//如果tmpVec中的数没有下层节点，则弹出
while(!tmpVec.empty() && tmpVec.back() == candidates[canSize - 1]) {
n--;
sum -= tmpVec.back();
tmpVec.pop_back();
}
//当前数的所有可能成功的情况都验证完，弹出该数，准备弹出sta中该数下层的剩余数，并在tmpVec压入与该数同层的下一个数
if (!tmpVec.empty()) {
n--;
sum -= tmpVec.back();
tmpVec.pop_back();
}
//如果curNum是candidates中的最后一个数，说明与curNum同层的所有数都验证完，不需要在sta中进行弹出与该数同层的所有剩余数的操作
if (curNum == candidates[canSize - 1])
continue;
if (sta.empty())
break;
//弹出sta中与curNum同层的所有剩余数
int tmpNum = sta.top();
sta.pop();
if (sta.empty() && curNum >= tmpNum)
sta.push(tmpNum);
else {
while (!sta.empty() && tmpNum < sta.top()) {
tmpNum = sta.top();
sta.pop();
}
}
}
else {
if (n == target / candidates[i]) {
while (!tmpVec.empty() && tmpVec.back() == candidates[canSize - 1]) {
n--;
sum -= tmpVec.back();
tmpVec.pop_back();
}
if (!tmpVec.empty()) {
sum -= tmpVec.back();
tmpVec.pop_back();
n--;
}
continue;
}
for (int j = i; j < canSize; j++)
if (candidates[j] == curNum) {
for (int k = canSize - 1; k >= j; k--)
sta.push(candidates[k]);
break;
}
}
}
}
return res;
}
``````

};

• Thank you for your sharing! But the naming of your code is a little bit hard to understand for me. Could you please explain your algorithm briefly?

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