-
Notifications
You must be signed in to change notification settings - Fork 55
Expand file tree
/
Copy pathEqualSumPartition.java
More file actions
80 lines (74 loc) · 3.63 KB
/
EqualSumPartition.java
File metadata and controls
80 lines (74 loc) · 3.63 KB
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* PROBLEM STATEMENT : DIVIDE THE ARRAY INTO TWO PARTITION OF EQUAL SUM.
//Key Points :
1 : THE PROBLEM IS SIMILAR TO THE SUBSET SUM PROBLEM WITH A LIITLE MODIFICATION
ARRAY ARR(2s)
/ \
/ \
/ \
Partition 1 Partition 2
Sum : s Sum : s
2 : WE CONCLUDE THAT THE SUM OF ARRAY SHOULD BE EVEN TO BE ABLE TO PARTIONED.
3 : IT IS SIMILAR TO SUBSET SUM PROBLEM AS WE NEED TO FIND A SUBSET OF SUM sum/2.
*/
public class EqualSumPartition {
//***********************************************Recursive Approach**********************************************************
private static boolean solveRecursively(int arr[], int i, int sum) {
//If at some point we have (sum == 0) it means we have found a subset of given sum in the array.So we return true
if (sum == 0) {
return true;
}
//The i == 0 will get executed only when we have no more elements left in the array and we couldnt find the required sum. So we return false;
if (i == 0) {
return false;
}
//If the given element is valid i.e it is less than our required sum. We solve the problem recursively. We have two possible choice:
//Include the element OR exclude it.
if (arr[i - 1] <= sum) {
return solveRecursively(arr, i - 1, sum - arr[i - 1]) | solveRecursively(arr, i - 1, sum);
} else {
return solveRecursively(arr, i - 1, sum); //As the element is invalid we do not include
}
}
//***********************************************Dynamic Programming Approach**********************************************************
private static boolean solveUsingDp(int arr[], int sum) {
//The bottom up dynamic programming approach is similar to the subset sum problem.
//The state dp[i][j] will be true if there a subset of first i items with sum value = j.
boolean dp[][] = new boolean[arr.length + 1][sum + 1];
for (int i = 0; i < arr.length + 1; i++) {
for (int j = 0; j < sum + 1; j++) {
if (i == 0 || j == 0) //base case. Evident from our recurive approah
{
if (i == 0) // the case when there are no it
{
dp[i][j] = false;
}
if (j == 0) {
dp[i][j] = true; //The case when sum = 0. We always have a empty subset {} with sum 0.
}
} else {
if (arr[i - 1] <= j) //If the element is valid. We will find subset of sum j by including or excluding the ith item
{
dp[i][j] = dp[i - 1][j - arr[i - 1]] | dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j]; //We dont include the ith item as its invalid
}
}
}
}
return dp[arr.length][sum];
}
public static void main(String[] args) {
int arr[] = {1, 2, 3, 6}, sum = 0;
//We find the sum of each element of array.
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
//As explained at top : A partition with equal sum would only exist when the sum is an even number
if (sum % 2 != 0) {
System.out.println(0);
} else {
System.out.println(solveRecursively(arr, arr.length, sum / 2)); //Recursive Approach
System.out.println(solveUsingDp(arr, sum / 2)); //Bottom up dynamic programming approach.
}
}
}