698 Partition to K Equal Sum Subsets
1. Question
Given an array of integersnums
and a positive integerk
, find whether it's possible to divide this array intok
non-empty subsets whose sums are all equal.
Example 1:
Input:
nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output:
True
Explanation:
It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:
1 <= k <= len(nums) <= 16
.
0 < nums[i] < 10000
.
2. Implementation
(1) Backtracking
思路:
(1) 要将nums数组分成k个和相等的subset,第一步当然是求nums中的数的和sum,如果sum能被k除不为0,则这个nums不可能分成k个和相等的subset
(2)接下来就是通过递归方式求出是否存在k个和相等的subset,这里用两个base case:
a. 当group为1时,说明剩下的数可以组成一个subset,这时直接返回true
b. 当curSum等于target时,我们找到一个符合条件的group, 下一步就是从数组的开头重头开始搜索符合的条件的下一个group
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length <= k) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
boolean[] used = new boolean[nums.length];
return canPartitionKSubsets(nums, k, sum / k, 0, 0, used);
}
public boolean canPartitionKSubsets(int[] nums, int group, int target, int start, int curSum, boolean[] used) {
// Only one group left, we can use the remaining numbers to form the subset
if (group == 1) {
return true;
}
// If current sum equals to target, we find a subset, restart the search from the beginning of nums to find the
// next valid subset
if (curSum == target) {
return canPartitionKSubsets(nums, group - 1, target, 0, 0, used);
}
for (int i = start; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
if (canPartitionKSubsets(nums, group, target, i + 1, curSum + nums[i], used)) {
return true;
}
used[i] = false;
}
}
return false;
}
}
3. Time & Space Complexity
时间复杂度O(2^n), 最坏情况是搜索所有可能的subset,总共有2^n个,空间复杂度O(n)
Last updated
Was this helpful?