C++ DP method(Accepted) & Backtracking (Memory Limit Exceeded)


  • 1

    DP method is very clear and simple. It is similar like recursive method.

    code block

    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1,0);
        dp[0] = 1;
        for(int i = 1;i<=target;i++){//for each sub-target, we want to find out the number of combination
            for(int num:nums){
                if(i>=num){dp[i] = dp[i]  +  dp[i-num];}
            }
        }
        return dp[target];
    }
    

    I first used the backtracking method, which is Memory Limit Exceeded when our target goes very large, but if this problem requires you output the combinations, the backtracking method is very useful. (Only for positive number)

    code block

    int combinationSum4(vector<int>& nums, int target) {
        vector<int> path;
        vector<vector<int>> res;
        find(nums,target,path,res);
        return res.size();//or you can change it to output the vector res.
    }
    
    void find(vector<int>& nums, int target, vector<int>& path, vector<vector<int>>& res){
        if (target == 0) { res.push_back(path); return;}
        else if (target < 0 ) return;
        for(int i = 0;i<nums.size();i++){
            path.push_back(nums[i]);
            find(nums, target - nums[i], path, res);
            path.pop_back();
        }
    }

  • 0
    T
    This post is deleted!

Log in to reply
 

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