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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// 77. Combinations
#include <stdio.h>
#include <stdlib.h>
/*
* 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
*/
long factorial(int n) {
if (n == 1 || n == 0)
return 1;
else
return n * factorial(n - 1);
}
void process(int **ans, int *idx, int *data, int n, int k, int pos, int curr) {
int i, j;
if (pos == k) {
for (i = 0; i < k; i++)
ans[*idx][i] = data[i];
(*idx)++;
return;
}
for (i = curr; i <= n - k + 1 + pos; i++) {
data[pos] = i;
process(ans, idx, data, n, k, pos + 1, i + 1);
}
}
int **combine(int n, int k, int *return_size, int **return_colum_size) {
int i, j;
long long c = 0;
c = factorial(n) / factorial(k) * factorial(n - k);
*return_colum_size = (int *)malloc(c * sizeof(int));
*return_size = c;
int **ans = (int **)malloc(c * sizeof(int *));
for (i = 0; i < c; i++) {
ans[i] = (int *)calloc(k, sizeof(int));
return_colum_size[0][i] = k;
}
int *data = (int *)malloc(k * sizeof(int));
int *idx = (int *)malloc(sizeof(int));
*idx = 0;
process(ans, idx, data, n, k, 0, 1);
free(data), free(idx);
return ans;
}
int main() {
int **c1 = combine(4, 2, NULL, NULL);
int **c2 = combine(1, 1, NULL, NULL);
for (int i = 0; i < 6; i++)
for (int j = 0; j < 2; j++)
printf("%d", c1[i][j]); //[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
printf("\n");
for (int i = 0; i < 1; i++)
for (int j = 0; j < 1; j++)
printf("%d", c2[i][j]); //[[1]]
printf("\n");
}
|