Matchsticks to Square
给一个数组, 问能不能用其中的数, 组成一个正方形. 能组成正方形,就是四等分. 所以穷举即可.
|
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 |
public class Solution { public boolean makesquare(int[] nums) { if(nums == null || nums.length < 4) return false; int sum = 0; for(int n : nums) sum += n; if(sum%4 != 0) return false; Arrays.sort(nums); reverse(nums); return dfs(nums, new int[4], sum/4, 0); } public boolean dfs(int[] nums, int[] sum, int target, int index) { if(nums.length == index){ if(sum[0] == target && sum[1] == target && sum[2] == target && sum[3] == target) return true; else return false; } for(int i = 0 ; i < 4; i++) { if(sum[i]+nums[index] <= target){ sum[i] += nums[index]; if(dfs(nums,sum,target,index+1)) return true; sum[i] -= nums[index]; } } return false; } private void reverse(int[] nums) { int i = 0, j = nums.length - 1; while (i < j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; j--; } } } |