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