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


  • 0
    A
    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;
    }
    

    };


  • 0
    B

    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?


Log in to reply
 

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