Untitled
unknown
plain_text
2 months ago
2.3 kB
4
Indexable
import java.util.Arrays; class Solution { public boolean canPartitionKSubsets(int[] nums, int k) { int sum = 0; for (int num : nums) { sum += num; } if (sum % k != 0) { return false; } int target = sum / k; // Sort in descending order for optimization. Arrays.sort(nums); reverse(nums); // Quick check: if the largest number is greater than target, partitioning is impossible. if (nums[0] > target) { return false; } int[] buckets = new int[k]; return search(nums, 0, buckets, target); } private boolean search(int[] nums, int index, int[] buckets, int target) { if (index == nums.length) { // When all numbers have been assigned, check that every bucket sums to target. for (int bucket : buckets) { if (bucket != target) { return false; } } return true; } // Try to assign nums[index] to each bucket. for (int i = 0; i < buckets.length; i++) { // If placing nums[index] in bucket[i] exceeds target, skip. if (buckets[i] + nums[index] > target) { continue; } // Avoid duplicate work: if a bucket is empty, then placing the current number in any other empty bucket is equivalent. if (i > 0 && buckets[i] == buckets[i - 1]) { continue; } buckets[i] += nums[index]; if (search(nums, index + 1, buckets, target)) { return true; } buckets[i] -= nums[index]; // backtrack // If this bucket is still empty after backtracking, no need to try further empty buckets. if (buckets[i] == 0) { break; } } return false; } private void reverse(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } }
Editor is loading...
Leave a Comment