-
Notifications
You must be signed in to change notification settings - Fork 0
/
EqualSumSubsets.java
34 lines (31 loc) · 1018 Bytes
/
EqualSumSubsets.java
1
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
29
30
31
32
33
34
public class EqualSumSubsets {
static boolean canPartition(int nums[], int k) {
int sum = 0;
for (int i : nums)
sum += i;
if (sum % k == 0)
return solve(nums, k, sum / k, 0, sum, new boolean[nums.length], 0);
return false;
}
static boolean solve(int nums[], int k, int target, int curr, int sum, boolean vis[], int idx) {
if (k == 1)
return true;
if (curr == target) {
return solve(nums, k - 1, target, 0, sum, vis, 0);
}
for (int i = idx; i < nums.length; i++) {
if (vis[i])
continue;
vis[i] = true;
if (solve(nums, k, target, curr + nums[i], sum, vis, i + 1))
return true;
// backtrack
vis[i] = false;
}
return false;
}
public static void main(String[] args) {
int nums[] = { 4, 3, 2, 3, 5, 2, 1 }, k = 4;
System.out.println(canPartition(nums, k));
}
}