Why DP is slower in this problem


  • 0
    J

    This is my code for the problem using DP, but why it is slower than None-DP methods

    class Solution {
        public:
            vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
                unordered_map<int, vector<vector<int>> > map;
                sort(candidates.begin(), candidates.end());
                for(int i =0; i < candidates.size(); i++){
                    for(int j =0; j <target+1;j++){
                        if(j>candidates[i]){
                            vector<vector<int>> tmp2(map[j-candidates[i]]);  
                            for(int k=0; k < tmp2.size();k++){
                                (tmp2[k]).push_back(candidates[i]);
                                (map[j]).push_back(tmp2[k]);
                            }
                        }else if (j == candidates[i]){
                            (map[j]).push_back(vector<int>(1,j));
                        }
                    }
                }
                
                return map[target];
            }
        };

Log in to reply
 

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