forked from deepanshumishra/JavaAndCPP_programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPartitionProblem.java
More file actions
64 lines (55 loc) · 1.49 KB
/
Copy pathPartitionProblem.java
File metadata and controls
64 lines (55 loc) · 1.49 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
// A recursive Java solution for partition problem
import java.io.*;
class Partition {
// A utility function that returns true if there is a
// subset of arr[] with sun equal to given sum
static boolean isSubsetSum(int arr[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum, then ignore
// it
if (arr[n - 1] > sum)
return isSubsetSum(arr, n - 1, sum);
/* else, check if sum can be obtained by any of
the following
(a) including the last element
(b) excluding the last element
*/
return isSubsetSum(arr, n - 1, sum)
|| isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
// Returns true if arr[] can be partitioned in two
// subsets of equal sum, otherwise false
static boolean findPartition(int arr[], int n)
{
// Calculate sum of the elements in array
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// If sum is odd, there cannot be two subsets
// with equal sum
if (sum % 2 != 0)
return false;
// Find if there is subset with sum equal to half
// of total sum
return isSubsetSum(arr, n, sum / 2);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 1, 5, 9, 12 };
int n = arr.length;
// Function call
if (findPartition(arr, n) == true)
System.out.println("Can be divided into two "
+ "subsets of equal sum");
else
System.out.println(
"Can not be divided into "
+ "two subsets of equal sum");
}
}