Algorithms/Java/Dynamic-Programming/PartitionProblem.java at main · Kumar-laxmi/Algorithms · GitHub

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
importjava.util.Arrays;
importjava.util.Scanner;

classPartitionProblem
{
// Returns true if there exists a subarray of array `nums[0…n]`
// with the given sum
publicstaticbooleansubsetSum(int[] nums, intn, intsum)
 {
// return true if the sum becomes 0 (subset found)
if (sum == 0) {
returntrue;
 }

// base case: no items left or sum becomes negative
if (n < 0 || sum < 0) {
returnfalse;
 }

// Case 1. Include the current item `nums[n]` in the subset and recur
// for remaining items `n-1` with the remaining total `sum-nums[n]`
booleaninclude = subsetSum(nums, n - 1, sum - nums[n]);

// return true if we get subset by including the current item
if (include) {
returntrue;
 }

// Case 2. Exclude the current item `nums[n]` from the subset and recur for
// remaining items `n-1`
booleanexclude = subsetSum(nums, n - 1, sum);

// return true if we get subset by excluding the current item
returnexclude;
 }

// Returns true if given array `nums[0…n-1]` can be divided into two
// subarrays with equal sum
publicstaticbooleanpartition(int[] nums)
 {
intsum = Arrays.stream(nums).sum();

// return true if the sum is even and the array can be divided into
// two subarrays with equal sum
return (sum & 1) == 0 && subsetSum(nums, nums.length - 1, sum/2);
 }

publicstaticvoidmain(String[] args)
 {
// Input: a set of items
Scannersc = newScanner(System.in);
intn = 0;
System.out.println("Enter size of array");
n=sc.nextInt();
int[] nums = newint[n];
System.out.println("Enter elements of array");
for(inti=0; i<n; i++)
 {
//reading array elements from the user
nums[i]=sc.nextInt();
 }

if (partition(nums)) {
System.out.println("Set can be partitioned");
 }
else {
System.out.println("Set cannot be partitioned");
 }
sc.close();
 }
}