-
Notifications
You must be signed in to change notification settings - Fork 0
/
L077_Combinations.c
80 lines (70 loc) · 1.76 KB
/
L077_Combinations.c
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
url: leetcode.com/problems/combinations/
AC 33ms 97.06%
*/
#include <stdio.h>
#include <stdlib.h>
typedef int* T;
typedef struct al sal;
typedef struct al * pal;
struct al {
int capacity;
int size;
T* arr;
};
pal al_init(int capacity) {
pal l = (pal) malloc(sizeof(sal));
if (capacity < 1) return NULL;
l->arr = (T*) malloc(sizeof(T) * capacity);
l->capacity = capacity;
l->size = 0;
return l;
}
void al_expand_capacity(pal l) {
T* new_arr = (T*) malloc(sizeof(T) * (l->capacity * 2 + 1));
int i = 0;
for (i = 0; i < l->capacity; i ++)
new_arr[i] = l->arr[i];
free(l->arr);
l->arr = new_arr;
l->capacity = l->capacity * 2 + 1;
}
void al_add_last(pal l, T v) {
if (l->capacity == l->size) al_expand_capacity(l);
l->arr[l->size] = v;
l->size ++;
}
T* al_convert_to_array_free_l(pal l) {
T* arr = l->arr;
free(l);
return arr;
}
int* arr_copy(int* save, int n) {
int* copy = (int*) malloc(sizeof(int) * n);
int i = 0;
for (i = 0; i < n; i ++)
copy[i] = save[i];
return copy;
}
void search(int ni, int n, int* save, int si, int sn, pal l) {
int k = 0;
if (si == sn) {
al_add_last(l, arr_copy(save, sn));
return;
}
for (k = ni; k <= n; k ++) {
save[si] = k;
search(k+1, n, save, si+1, sn, l);
}
}
int** combine(int n, int k, int** cn, int* ren) {
pal l = al_init(16);
int i = 0;
int* save = (int*) malloc(sizeof(int) * k);
search(1, n, save, 0, k, l);
*ren = l->size;
*cn = (int*) malloc(sizeof(int) * l->size);
for (i = 0; i < l->size; i ++)
(*cn)[i] = k;
return al_convert_to_array_free_l(l);
}