473. Matchsticks to Square 发表于 2022-08-14 DFS123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { public boolean makesquare(int[] matchsticks) { return canPartitionKSubsets(matchsticks, 4); } public boolean canPartitionKSubsets(int[] nums, int k) { int sum = Arrays.stream(nums).sum(); if (sum % k != 0) { return false; } int targetSum = sum / k; Arrays.sort(nums); boolean[] used = new boolean[nums.length]; return dfs(nums, used, nums.length - 1, 0, targetSum, k); } private boolean dfs(int[] nums, boolean[] used, int startIndex, int sum, int targetSum, int k) { if (k == 1) { // 当剩余最后一个集合时,无需遍历到底 return true; } if (sum == targetSum) { return dfs(nums, used, nums.length - 1, 0, targetSum, k - 1); } for (int i = startIndex; i >= 0; i--) { if (used[i] || sum + nums[i] > targetSum || (i + 1 < nums.length && !used[i + 1] && nums[i] == nums[i + 1])) { continue; } used[i] = true; if (dfs(nums, used, i - 1, sum + nums[i], targetSum, k)) { return true; } used[i] = false; } return false; }} DFS12345678910111213141516171819202122232425262728293031323334353637class Solution { public boolean makesquare(int[] matchsticks) { return canPartitionKSubsets(matchsticks, 4); } public boolean canPartitionKSubsets(int[] nums, int k) { int sum = Arrays.stream(nums).sum(); if (sum % k != 0) { return false; } int targetSum = sum / k; Arrays.sort(nums); int[] collections = new int[k]; return dfs(nums, nums.length - 1, targetSum, collections); } private boolean dfs(int[] nums, int index, int targetSum, int[] collections) { if (index == -1) { return true; } for (int i = 0; i < collections.length; i++) { if (collections[i] + nums[index] > targetSum || (i > 0 && collections[i] == collections[i - 1])) { continue; } collections[i] += nums[index]; if (dfs(nums, index - 1, targetSum, collections)) { return true; } collections[i] -= nums[index]; } return false; }} Reference473. Matchsticks to Square698. Partition to K Equal Sum Subsets