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:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

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}$ , 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43