aboutsummaryrefslogtreecommitdiff
path: root/subsets2.c
blob: f29b3b9ff965bec7ab602143abc49545e3255249 (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
63
64
65
66
67
68
69
70
71
72
73
74
// 90. Subsets II
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * given an integer array 'nums' that may contain duplicates, return all
 * possible subsets (the power set). the solution set must not contain duplicate
 * subsets. return the solution in any order.
 */

void process(int **res, int *idx, int *data, int pos, int **nums, int nums_size,
             int *cols) {
  if (!nums_size) {
    cols[*idx] = pos;
    if (!pos) {
      (*idx)++;
      return;
    }
    res[*idx] = malloc(pos * sizeof(int));
    memcpy(res[*idx], data, pos * sizeof(int));
    (*idx)++;
    return;
  }
  for (int i = 0; i <= nums[0][1]; i++) {
    if (!i)
      process(res, idx, data, pos, &nums[1], nums_size - 1, cols);
    else {
      data[pos] = nums[0][0];
      pos++;
      process(res, idx, data, pos, &nums[1], nums_size - 1, cols);
    }
  }
}

int **subsetsWithDup(int *nums, int nums_size, int *return_size,
                     int **return_col_size) {
  int **ans = malloc(1024 * sizeof(int *));
  return_col_size[0] = malloc(1024 * sizeof(int));
  int *data = malloc(10 * sizeof(int));
  int *idx = calloc(1, sizeof(int));
  int *hash = calloc(21, sizeof(int));
  for (int i = 0; i < nums_size; i++)
    hash[nums[i] + 10]++;
  int **n_nums = malloc(nums_size * sizeof(int *));
  int n_nums_size = 0;
  for (int i = 0; i < 21; i++)
    if (hash[i]) {
      n_nums[n_nums_size] = malloc(2 * sizeof(int));
      n_nums[n_nums_size][0] = i - 10;
      n_nums[n_nums_size][1] = hash[i];
      n_nums_size++;
    }
  free(hash);
  process(ans, idx, data, 0, n_nums, n_nums_size, *return_col_size);
  ans = realloc(ans, (*idx) * sizeof(int *));
  return_col_size[0] = realloc(return_col_size[0], (*idx) * sizeof(int));
  *return_size = *idx;
  return ans;
}

int main() {
  int n1[] = {1, 2, 2}, n2[] = {0};
  int **swd1 = subsetsWithDup(n1, 3, NULL, NULL);
  int **swd2 = subsetsWithDup(n2, 1, NULL, NULL);
  for (int i = 0; i < 6; i++)
    for (int j = 0; j < 3; j++)
      printf("%d ", swd1[i][j]);
  printf("\n");
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 1; j++)
      printf("%d ", swd2[i][j]);
  printf("\n");
}