Any different between these two solutions?


  • 0
    T
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            std::sort(candidates.begin(), candidates.end());
            vector<int> temp_result;
            vector<vector<int>> results;
            //dfs(candidates, target, temp_result, results);
            new_dfs(candidates, 0, target, temp_result, results);
            return results;
        }
        void new_dfs(vector<int> &candidates, int id, int target, vector<int> &temp_result, vector<vector<int>> & results){
            if(target==0 && temp_result.size()>0){
                results.push_back(temp_result);
                return;
            }
            if(id >= candidates.size() || candidates[id] > target)
                return;
            temp_result.push_back(candidates[id]);
            new_dfs(candidates, id, target-candidates[id], temp_result, results);
            temp_result.pop_back();
            new_dfs(candidates, id+1, target, temp_result, results);
    
        }
    }
    

    The above solution runs well for the OJ, I think the solution should be the same if I replace snippet A with snippet B:

    Snippet A:

       temp_result.push_back(candidates[id]);
       new_dfs(candidates, id, target-candidates[id], temp_result, results);
       temp_result.pop_back();
       new_dfs(candidates, id+1, target, temp_result, results);
    

    Snippet B:

       new_dfs(candidates, id+1, target, temp_result, results);
       temp_result.push_back(candidates[id]);
       new_dfs(candidates, id, target-candidates[id], temp_result, results);
    

    However, Snippet B failed with "Output Limit Exceeded", Last executed input:
    [92,71,89,74,102,91,70,119,86,116,114,106,80,81,115,99,117,93,76,77,111,110,75,104,95,112,94,73]

    Can anyone give any hints on what happened?


Log in to reply
 

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