Very intuitive solution accepted as best in C, well-explained


  • 0

    According to the problem, we have several rules to hack it:

    • no duplicate in the same set -> using a start index to move forward no backward;
    • cover all possible sets -> move one step each move in each round till the end and then move to the next in the previous round;
    • the number of a set should be limited to k -> checking the stack each time and when it's the time, collect the stack and end the current round;

    Bang. End of story!

    • Space complexity will O(k*n^k) since there will be n^k sets and each set will contain k elements;
    • Time complexity will be the same as space since each set will be collected from the stack of size k and there are n^k sets in all;

    void traverse(int* nums, int size, int begin, int k, int* stack, int top, int*** arr, int** colSize, int* returnSize)
    {
        if(top+1==k)
        {
            *returnSize += 1;
            *colSize = (int*)realloc(*colSize, sizeof(int)*(*returnSize));
            (*colSize)[*returnSize-1] = k;
            *arr = (int**)realloc(*arr, sizeof(int*)*(*returnSize));
            (*arr)[*returnSize-1] = (int*)malloc(sizeof(int)*k);
            for(int i = 0; i < k; i++)
                (*arr)[*returnSize-1][i] = stack[i];
            return ;
        }
        for(int i = begin; i < size; i++)
        {
            stack[top+1] = nums[i];
            traverse(nums, size, i+1, k, stack, top+1, arr, colSize, returnSize);
        }
    }
    
    //AC - 4ms;
    int** combine(int n, int k, int** colSize, int* returnSize)
    {
        int *nums = (int*)malloc(sizeof(int)*n);
        for(int i = 0; i < n; i++)
            nums[i] = i+1;
        int *stack = (int*)malloc(sizeof(int)*k);
        int top = -1;
        *returnSize = 0;
        int **arr = (int**)malloc(sizeof(int*));
        for(int i = 0; i <= n-k; i++)
        {
            stack[top+1] = nums[i];
            traverse(nums, n, i+1, k, stack, top+1, &arr, colSize, returnSize);
        }
        return arr;
    }

Log in to reply
 

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