Description
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 |
Note:
- 1 <= k <= len(nums) <= 16.
- 0 < nums[i] < 10000.
Solution
Solution 1: DFS, but slower1
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
29class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums.length < k) return false;
Arrays.sort(nums);
int sum = 0;
for (int num: nums) sum += num;
if (sum % k != 0) return false;
return helper(nums, sum / k, new int[k], nums.length-1);
}
public boolean helper(int[] nums, int target, int[] parts, int index){
if (index == -1){
boolean flag = true;
for (int part: parts){
if (part != target){
flag = false;
break;
}
}
return flag;
}
for (int i = 0; i < parts.length; i++){
if (parts[i] + nums[index] > target) continue;
parts[i] += nums[index];
if (helper(nums, target, parts, index - 1)) return true;
parts[i] -= nums[index];
}
return false;
}
}
Solution 2: Still DFS, but faster1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public boolean canPartitionKSubsets(int[] A, int k) {
if (k > A.length) return false;
int sum = 0;
for (int num : A) sum += num;
if (sum % k != 0) return false;
boolean[] visited = new boolean[A.length];
Arrays.sort(A);
return helper(A, 0, A.length - 1, visited, sum / k, k);
}
public boolean helper(int[] A, int sum, int st, boolean[] visited, int target, int round) {
if (round == 0) return true;
if (sum == target && helper(A, 0, A.length - 1, visited, target, round - 1))
return true;
for (int i = st; i >= 0; --i) {
if (!visited[i] && sum + A[i] <= target) {
visited[i] = true;
if (helper(A, sum + A[i], i - 1, visited, target, round))
return true;
visited[i] = false;
}
}
return false;
}
}