LeetCode //C - 77. Combinations

77. Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Example 2:

Constraints:

1 <= n <= 20
1 <= k <= n

From: LeetCode
Link: 77. Combinations

Solution:

Ideas：

1. DFS Function (dfs):

This function recursively constructs the combinations.
If the current combination size (currentSize) is equal to k, the combination is complete. We copy this combination to our results array and return.
If start exceeds n, it means we’ve crossed the limit of numbers available, so we return without making further decisions.
For each number start, we:
- Include it in the combination and recursively explore further numbers.
- Exclude it from the combination and recursively explore further numbers.

2. Main combine Function:

We initially allocate a large buffer (initialSize) for the results array to hold the combinations. The size is set to 2 20 2^{20} 220 , which is a safe upper bound given the constraints.
We call the dfs function to start constructing the combinations starting from the number 1.
After generating all combinations, we resize the results and returnColumnSizes arrays to the actual size of the generated combinations to conserve memory.

Code:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void dfs(int n, int k, int start, int* currentCombination, int currentSize, int*** results, int* resultSize, int** returnColumnSizes) {
    if (currentSize == k) {
        int* combination = (int*)malloc(sizeof(int) * k);
        for (int i = 0; i < k; i++) {
            combination[i] = currentCombination[i];
        }
        results[*resultSize] = combination;
        (*returnColumnSizes)[*resultSize] = k;
        (*resultSize)++;
        return;
    }
    
    if (start > n) return;
    
    // include the current number
    currentCombination[currentSize] = start;
    dfs(n, k, start + 1, currentCombination, currentSize + 1, results, resultSize, returnColumnSizes);
    
    // exclude the current number
    dfs(n, k, start + 1, currentCombination, currentSize, results, resultSize, returnColumnSizes);
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    int initialSize = 1 << 20; // 2^20
    int** results = (int**)malloc(sizeof(int*) * initialSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * initialSize);

    *returnSize = 0;
    int* currentCombination = (int*)malloc(sizeof(int) * k);
    dfs(n, k, 1, currentCombination, 0, results, returnSize, returnColumnSizes);
    free(currentCombination);

    // Resize to actual size
    results = (int**)realloc(results, sizeof(int*) * (*returnSize));
    *returnColumnSizes = (int*)realloc(*returnColumnSizes, sizeof(int) * (*returnSize));

    return results;
}

Navigator_Z