Comment on page

698.Partition-to-K-Equal-Sum-Subsets

698. Partition to K Equal Sum Subsets

题目地址

题目描述

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k 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.

代码

Approach #1 DFS

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k != 0) return false;
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
return dfs(nums, k, sum / k, 0, 0, visited);
}
​
private boolean dfs(int[] nums, int k, int target, int start, int curSum, boolean[] visited) {
if (k == 1) return true;
if (curSum > target) return false;
if (curSum == target) return dfs(nums, k - 1, target, 0, 0, visited);
for (int i = start; i < nums.length; i++) {
if (visited[i]) continue;
visited[i] = true;
if (dfs(nums, k, target, i + 1, curSum + nums[i], visited)) return true;
visited[i] = false; // 不能少
}
return false;
}
}

Approach #2 DFS + Greedy

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
// 1. compute the target sum for each set
int sum = Arrays.stream(nums).sum();
if (sum % k > 0) return false;
int target = sum / k;
// 2. sort
Arrays.sort(nums);
// 3. 从大到小prune等于target的elements
int row = nums.length - 1;
if (nums[row] > target) return false;
while (row >= 0 && nums[row] == target) {
row--;
k--;
}
​
return search(new int[k], row, nums, target);
}
​
private boolean search(int[] groups, int row, int[] nums, int target) {
if (row < 0) return true;
int v = nums[row];
for (int i = 0; i < groups.length; i++) {
if (groups[i] + v <= target) {
groups[i] += v;
if (search(groups, row - 1, nums, target)) return true;
groups[i] -= v;
}
if (groups[i] == 0) break; // in the first run of search, we will make only 1 recursive call, instead of k
}
return false;
}
​
}

Approach #3 Dynamic Programming Confusion

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int N = nums.length;
Arrays.sort(nums);
int sum = Arrays.stream(nums).sum();
int target = sum / k;
if (sum % k > 0 || nums[N - 1] > target) return false;
​
boolean[] dp = new boolean[1 << N];
dp[0] = true;
int[] total = new int[1 << N];
​
for (int state = 0; state < (1 << N); state++) {
if (!dp[state]) continue;
for (int i = 0; i < N; i++) {
int future = state | (1 << i); // 把state的第 i 位置为 1
if (state != future && !dp[future]) {
if (nums[i] <= target - (total[state] % target)) {
dp[future] = true;
total[future] = total[state] + nums[i];
} else {
break;
}
}
}
}
return dp[(1 << N) - 1];
}
}

Approach #4 TLE

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k != 0) return false;
Arrays.sort(nums);
return dfs(nums, sum / k, 0, k, 0);
}
​
private boolean dfs(int[] nums, int target, int cur, int k, int used) {
if (k == 0) return used == (1 << nums.length) - 1;
for (int i = 0; i < nums.length; ++i) {
if ((used & (1 << i)) == 1) continue;
int t = cur + nums[i];
if (t > target) break; // Important
int new_used = used | (1 << i);
if (t == target && dfs(nums, target, 0, k - 1, new_used)) {
return true;
} else if (dfs(nums, target, t, k, new_used)){
return true;
}
}
return false;
}
};