aboutsummaryrefslogtreecommitdiff
path: root/combination_sum2.c
blob: 6d20d09fd11c392ca6eb0b058c0f3d306a69fc89 (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
// 40. Combination Sum II
#include "leetcode.h"

/*
 * given a collection of candidate numbers and a target number, find all unique
 * combinations in 'candidates' where the candidate numbers sum to 'target'.
 * each number in 'candidates' may only be used once
 */

int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }

void dfs(int *candidates, int candidatesSize, int target, int idx, int *curr,
         int currSize, int *returnSize, int **returnColumnSizes, int ***res) {
  int prev = 0;
  for (int i = idx; i < candidatesSize; i++) {
    if (candidates[i] == target) {
      (*returnSize)++;
      *res = (int **)realloc(*res, (*returnSize) * sizeof(int *));
      (*res)[(*returnSize) - 1] = (int *)malloc((currSize + 1) * sizeof(int));
      memcpy((*res)[(*returnSize) - 1], curr, currSize * sizeof(int));
      (*res)[(*returnSize) - 1][currSize] = candidates[i];
      (*returnColumnSizes) =
          (int *)realloc((*returnColumnSizes), (*returnSize) * sizeof(int));
      (*returnColumnSizes)[(*returnSize) - 1] = currSize + 1;
      break;
    } else if (candidates[i] <= (target / 2) && candidates[i] != prev) {
      curr[currSize] = candidates[i];
      dfs(candidates, candidatesSize, target - candidates[i], i + 1, curr,
          currSize + 1, returnSize, returnColumnSizes, res);
      prev = candidates[i];
    } else if (candidates[i] > target)
      break;
  }
}

int **combinationSum2(int *candidates, int candidatesSize, int target,
                      int *returnSize, int **returnColumnSizes) {
  qsort(candidates, candidatesSize, sizeof(int), cmp);
  int *curr = (int *)malloc(100 * sizeof(int)), currSize = 0;
  int **ans = (int **)malloc(sizeof(int *));
  (*returnColumnSizes) = (int *)malloc(sizeof(int));
  (*returnSize) = 0;
  dfs(candidates, candidatesSize, target, 0, curr, currSize, returnSize,
      returnColumnSizes, &ans);
  free(curr);
  return ans;
}

int main() {
  int c1[] = {10, 1, 2, 7, 6, 1, 5}, c2[] = {2, 5, 2, 1, 2}, rs1, rs2;
  int *rcs1 = (int *)malloc(ARRAY_SIZE(c1) * sizeof(int));
  int *rcs2 = (int *)malloc(ARRAY_SIZE(c2) * sizeof(int));
  int **cs21 = combinationSum2(c1, ARRAY_SIZE(c1), 8, &rs1, (int **)rcs1);
  int **cs22 = combinationSum2(c2, ARRAY_SIZE(c2), 5, &rs2, (int **)rcs2);
  for (int i = 0; i < rs2; i++)
    for (int j = 0; j < rcs2[i]; j++)
      printf("%d ", cs22[i][j]);
  printf("\n");
  free(cs21), free(cs22), free(rcs1), free(rcs2);
}