C dfs solution


  • 0
    V

    Removing the duplicated ones in C is really not convenient, that part looks ugly.

    /**
     * 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 n, int f, int d, int *sz, int ***result, int **col, int *num) {
        int i, j, k;
        int *buf;
    
        j = *num;
        for (i = f; i < n; i ++) {
            if (!(n % i)) {
                dfs(n / i, i, d + 1, sz, result, col, num);
                while (j < *num) {
                    buf = (*result)[j];
                    buf[d] = i;
                    j ++;
                }
            }
        }
        
        if (n <= f || (n % f)) {
            if (d > 0) {
                // found one
                buf = malloc((d + 1) * sizeof(int));
                //assert(buf);
                buf[d] = n;
                if(*num == *sz) {
                    *sz = (*sz) * 2;
                    *result = realloc(*result, (*sz) * sizeof(int *));
                    *col = realloc(*col, (*sz) * sizeof(int));
                    //assert(*result && *col);
                }
                (*result)[*num] = buf;
                (*col)[*num] = d + 1;
                (*num) ++;
            }
        }
    }
    
    int** getFactors(int n, int** columnSizes, int* returnSize) {
        int **result;
        int sz = 100;
        int i, j, k, x, y, z, *tmp;
    
        result = malloc(sz * sizeof(int *));
        *columnSizes = malloc(sz * sizeof(int));
        //assert(result && *columnSizes);
        
        *returnSize = 0;
        
        dfs(n, 2, 0, &sz, &result, columnSizes, returnSize);
        
        //remove duplicated ones
        for (i = 0; i < *returnSize; i ++) {
            do {
                z = 0;
                for (j = i + 1; j < *returnSize; j ++) {
                    if ((*columnSizes)[i] == (*columnSizes)[j]) {
                        x = y = 0;
                        for (k = 0; k < (*columnSizes)[i]; k ++) {
                            x += result[i][k];
                            y += result[j][k];
                        }
                        if (x == y) {
                            //found a dup
                            (*returnSize) --;
                            tmp = result[j];
                            result[j] = result[*returnSize];
                            (*columnSizes)[j] = (*columnSizes)[*returnSize];
                            free(tmp);
                            z = 1;
                        }
                    }
                }
            } while (z);
        }
    
        if (*returnSize == 0) {
            free(result);
            free(*columnSizes);
            result = NULL;
            *columnSizes = NULL;
        }
        
        return result;
    }
    

Log in to reply
 

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