Problems about Combination Sum III whit pure C solution


  • 0
    K

    I am trying to fix this problem with pure C, I always got an Runtime Error although it works well in my VS2010. And I am puzzled with the memory allocation in C especially when it in recursive process, any one can help me? Do I do the memory allocation right? or any suggestions, thank you!

    /**
     * Return an array of arrays of size *returnSize.
     * The sizes of the arrays are returned as *columnSizes array.
     * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
     */
     
    void dfs(int **ret,int *candidate,int *rindex,int *cindex,int k,int n,int index){
        if(n==0 && k==0){
            ret[*rindex] = (int*)malloc(sizeof(int)*(*cindex));
            for(int i=0;i<(*cindex);i++){
                ret[*rindex][i]=candidate[i];
            }
            (*rindex)++;
            int **tmp = (int **)realloc(ret,sizeof(int*)*((*rindex)+1));
            if(tmp != NULL){
                ret=tmp;
            }
            return;
        }
        if(index>9 || n<=0 || k<=0){
            return;
        }
        for(int i=index;i<=9;i++){
            if(i>n){
                break;
            }
            *(candidate+(*cindex))=i;
            (*cindex)++;
            dfs(ret,candidate,rindex,cindex,k-1,n-i,i+1);
            (*cindex)--;
        }
    }
      
    int** combinationSum3(int k, int n, int** columnSizes, int* returnSize) {
        int *candidate = (int*)malloc(sizeof(int)*k);
        memset(candidate,0,sizeof(candidate));
        int **ret = (int **)malloc(sizeof(int*));
        int rindex=0;
        int cindex=0;
        dfs(ret,candidate,&rindex,&cindex,k,n,1);
        *columnSizes = (int *)malloc(sizeof(int)*(rindex));
        for(int i=0;i<rindex;i++){
            (*columnSizes)[i]=k;
        }
        *returnSize=rindex;
        free(candidate);
        return ret;
    }

Log in to reply
 

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