aboutsummaryrefslogtreecommitdiff
path: root/subsets.c
blob: a1697e5bc15ab710befe6e5d599b9db5391a5202 (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
// 78. Subsets
#include "leetcode.h"

/*
 * given an integer array 'nums' of unique elements return all possible subsets
 * (the power set). the solution set must not contain duplicate subsets. return
 * the solution in any order.
 */

void dfs(int *nums, int numsSize, int **res, int *returnSize,
         int **returnColumnSizes, int *tmp, int target_size, int idx,
         int start) {
  if (idx == target_size) {
    *returnColumnSizes[*returnSize] = idx;
    res[*returnSize] = (int *)malloc(idx * sizeof(int));
    if (target_size)
      memcpy(res[*returnSize], tmp, idx * sizeof(int));
    (*returnSize)++;
  } else {
    for (int i = start; i < numsSize; i++) {
      tmp[idx] = nums[i];
      dfs(nums, numsSize, res, returnSize, returnColumnSizes, tmp, target_size,
          idx + 1, i + 1);
    }
  }
}

int **subsets(int *nums, int numsSize, int *returnSize,
              int **returnColumnSizes) {
  int size = pow(2, numsSize);
  *returnSize = 0;
  *returnColumnSizes = (int *)malloc(size * sizeof(int));
  int **ans = (int **)malloc(size * sizeof(int));
  int *tmp = (int *)malloc(numsSize * sizeof(int));
  for (int i = 0; i <= numsSize; i++)
    dfs(nums, numsSize, ans, returnSize, returnColumnSizes, tmp, i, 0, 0);
  free(tmp);
  return ans;
}

int main() {
  int n1[] = {1, 2, 3}, n2[] = {0}, rs1, rs2, **rcs1, **rcs2;
  int **s1 = subsets(n1, ARRAY_SIZE(n1), &rs1, rcs1);
  int **s2 = subsets(n2, ARRAY_SIZE(n2), &rs2, rcs2);
  for (int i = 0; i < rs1; i++)
    for (int j = 0; j < *rcs1[i]; j++)
      printf("%d ", s1[i][j]); // [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
  printf("\n");
  for (int i = 0; i < rs2; i++)
    for (int j = 0; j < *rcs2[i]; j++)
      printf("%d ", s2[i][j]); // expect: [[],[0]]
  printf("\n");
}