aboutsummaryrefslogtreecommitdiff
path: root/combinations.c
blob: 29df63917d218210b889331277d859ab2cdd3150 (plain)
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");
}