C++ DP solution but time exceeded.


  • 0
    L

    class Solution {

    public:

    vector<vector<int>> result;
    
    vector<int> middleResult;
    
    void combinationSum2Generating (vector<int>& candidates, int target, int start, int end) {
    
        if (target == 0) {
    
            result.push_back(middleResult);
    
        } else {
    
            // guess + resursion
    
            for (int i = start; i < end; i++) {
    
                middleResult.push_back(candidates[i]);
    
                combinationSum2Generating(candidates, target-candidates[i], i+1, end);
    
                middleResult.pop_back();
    
            }
    
        }
    
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    
        combinationSum2Generating(candidates, target, 0, candidates.size());
    
        return result;
    
    }
    

    };


  • 0
    L

    Any one could help ? why it is time-exceeded ?


  • 0
    L

    I tested this on coderPad, and the result is correct.


  • 0
    L

    class Solution {
    public:
    vector<vector<int>> result;
    vector<int> temp;

    void combinationSum2_sub (vector<int>& candidates,
                              int target,
                              int start,
                              int end) {
                                  
        if (target == 0) {
            if (find(result.begin(), result.end(), temp) == result.end()) {
                result.push_back(temp);
            }
            return;
        }
        
        if (target < candidates[start]) {
            return;
        }
        
        for (int i = start; i<end; i++) {
            temp.push_back(candidates[i]);
            combinationSum2_sub(candidates, target-candidates[i], i+1, end);
            temp.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // sort the array
        sort(candidates.begin(), candidates.end());
        combinationSum2_sub(candidates, target, 0, candidates.size());
        return result;
    }
    

    };


  • 0
    S

    you need to cut down on the extra cases, like if the sum > target, then stop processing further


  • 0
    J

    class Solution {
    public:
    vector<int>temp;
    vector<vector<int> >result;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        
        sumHelper(candidates,target,0,candidates.size());
        return result;
    }
    
    void sumHelper(vector<int>& candidates,int target,int index,int length){
        //index代表数组索引值,length代表数组长度
        if(target==0){
            //这里很巧的是,别人用sum求和,他不用,他是相减,只要等于0了,就会存入数组中。
            if(find(result.begin(),result.end(),temp)==result.end()){   
                result.push_back(temp);
            }
            return;//不需要返回
        }
        if(index>=length||target<0){//因为是求减法,如果不相等,立即返回||
                                   //还有一种是索引值大于数组长度
            return;
        }
        
        for(int i=index;i<=length-1;i++){
            temp.push_back(candidates[i]);
            sumHelper(candidates,target-candidates[i],i+1,length);
            temp.pop_back();
        }
    }
    

    };


  • 0
    A

    @laputa This is NOT DP! This is just simple recursive.


Log in to reply
 

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