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

• 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;
}``````

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