diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /matchsticks_square.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'matchsticks_square.c')
-rw-r--r-- | matchsticks_square.c | 61 |
1 files changed, 61 insertions, 0 deletions
diff --git a/matchsticks_square.c b/matchsticks_square.c new file mode 100644 index 0000000..7cb561f --- /dev/null +++ b/matchsticks_square.c @@ -0,0 +1,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 +} |