aboutsummaryrefslogtreecommitdiff
path: root/matchsticks_square.c
blob: 7cb561fffe65cd85b0ff426242c4ac098f32104c (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
// 473. Matchsticks to Square
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * given an integer array 'matchsticks' where 'matchsticks[i]' is the length of
 * the i'th matchstick. you want to use all the matchsticks to make one square.
 * you should not break any stick, but you can link them up, and each matchstick
 * can be used exactly one time. return 1 if you make square, 0 if not.
 */

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

bool dfs(int *nums, bool *visited, int curr, int n, int group, long long target,
         long long sum) {
  if (group == 4)
    return true;
  if (sum > target)
    return false;
  if (sum == target)
    return dfs(nums, visited, group, n, group + 1, target, 0);
  int last = -1;
  for (int i = curr; i < n; i++) {
    if (visited[i] == true)
      continue;
    if (nums[i] == last)
      continue;
    visited[i] = true;
    if (dfs(nums, visited, i + 1, n, group, target, sum + nums[i]) == true)
      return true;
    visited[i] = false;
    last = nums[i];
  }
  return false;
}

bool makeSquare(int *matchsticks, int matchsticksSize) {
  int n = matchsticksSize;
  bool ans;
  long long sum = 0;
  for (int i = 0; i < n; i++)
    sum += matchsticks[i];
  if (sum % 4 != 0)
    return false;
  long long target = sum / 4;
  qsort(matchsticks, n, sizeof(int), cmp);
  if (matchsticks[0] > target)
    return false;
  bool *visited = calloc(n, sizeof(bool));
  ans = dfs(matchsticks, visited, 0, n, 0, target, 0);
  free(visited);
  return ans;
}

int main() {
  int matchsticks1[] = {1, 1, 2, 2, 2}, ms1 = 5;
  int matchsticks2[] = {3, 3, 3, 3, 4}, ms2 = 5;
  printf("%d\n", makeSquare(matchsticks1, ms1)); // expect: 1
  printf("%d\n", makeSquare(matchsticks2, ms2)); // expect: 0
}