40 ms C, DP with cut branch


  • 0
    S
    int* gNums;
    int gSize;
    struct {
        int gNode;
        int gValue;   
    }gMap[10000];
    int gLen=1;
    void hashAdd(int node, int value){
        gMap[gLen].gNode=node;
        gMap[gLen].gValue=value;
        gLen++;
    }
    int hashSearch(int node){
        for(int i=0;i<gLen;i++){
            if (gMap[i].gNode==node)
            return gMap[i].gValue;
        }
        return -1;
    }
    int find(int t){
        int r;
        if ((r=hashSearch(t))!=-1){
            return r;
        }
        int r0=0;
        for (int i=0;i<gSize;i++){
            if (t-gNums[i]>=0)
            r0+=find(t-gNums[i]);
        }
        hashAdd(t,r0);
        return r0;
    }
    int combinationSum4(int* nums, int numsSize, int target) {
        gMap[0].gNode=0;
        gMap[0].gValue=1;
        gLen=1;
        gNums=nums;
        gSize=numsSize;
        
        return find(target);
    }

Log in to reply
 

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