DP based solution - Generate solution for k number using solutions from (k-1) numbers bottom up


  • 0
    S

    DP solution -
    We generate sub results for k-1 numbers and target value from 1 to target and then use that to generate results for k numbers

    
    vector<vector<int>> combinations(int target, int k) {
        
        vector<vector<vector<int>>>* localResultKMinus1 = new vector<vector<vector<int>>>(target+1);
        vector<vector<vector<int>>>* localResultK = new vector<vector<vector<int>>>(target+1);
        vector<vector<vector<int>>>* temp;
        
        for(int i=1; i<=target;i++) {
            localResultKMinus1->at(i) = {};
        }
        
        int cnt = 1;
        
        while(cnt <= k) {
            // clean up for the current run
            for(int i=1; i<=target;i++) {
              localResultK->at(i) = {};
            }
    
            for(int i=1;i<=target;i++) {
                for(int numIndex = 1; numIndex <= 9;numIndex++) {
                    if(numIndex > i) break;
                    vector<int> singleNum = {numIndex};
                    if (numIndex == i && cnt == 1) localResultK->at(i).push_back(singleNum);
    
                    vector<vector<int>> prevResult = localResultKMinus1->at(i-numIndex);
                        for(auto p = prevResult.begin(); p != prevResult.end(); p++) {
                            if(numIndex > (*p).back()) {
                              p->push_back(numIndex);
                              localResultK->at(i).push_back(*p);
                            }
                        }
                }
            }
            
            temp = localResultKMinus1;
            localResultKMinus1 = localResultK;
            localResultK = temp;
            cnt++;
        }
        
        
        return localResultKMinus1->at(target);
    }
    
    

Log in to reply
 

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