LeetCode 416 - Partition Equal Subset Sum
Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks
Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.
Read full article from Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks
Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks
Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.
The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array dp[n+1][sum+1] where n is number of elements in given set and sum is sum of all elements. We can construct the solution in bottom up manner.
The task is to divide the set into two parts. We will consider the following factors for dividing it. Let dp[n+1][sum+1] = {1 if some subset from 1st to i'th has a sum equal to j 0 otherwise} i ranges from {1..n} j ranges from {0..(sum of all elements)} So dp[n+1][sum+1] will be 1 if 1) The sum j is achieved including i'th item 2) The sum j is achieved excluding i'th item. Let sum of all the elements be S. To find Minimum sum difference, w have to find j such that Min{sum - j*2 : dp[n][j] == 1 } where j varies from 0 to sum/2 The idea is, sum of S1 is j and it should be closest to sum/2, i.e., 2*j should be closest to sum.
// Returns the minimum value of the difference of the two sets.
int
findMin(
int
arr[],
int
n)
{
// Calculate sum of all elements
int
sum = 0;
for
(
int
i = 0; i < n; i++)
sum += arr[i];
// Create an array to store results of subproblems
bool
dp[n+1][sum+1];
// Initialize first column as true. 0 sum is possible
// with all elements.
for
(
int
i = 0; i <= n; i++)
dp[i][0] =
true
;
// Initialize top row, except dp[0][0], as false. With
// 0 elements, no other sum except 0 is possible
for
(
int
i = 1; i <= sum; i++)
dp[0][i] =
false
;
// Fill the partition table in bottom up manner
for
(
int
i=1; i<=n; i++)
{
for
(
int
j=1; j<=sum; j++)
{
// If i'th element is excluded
dp[i][j] = dp[i-1][j];
// If i'th element is included
if
(arr[i-1] <= j)
dp[i][j] |= dp[i-1][j-arr[i-1]];
}
}
// Initialize difference of two sums.
int
diff = INT_MAX;
// Find the largest j such that dp[n][j]
// is true where j loops from sum/2 t0 0
for
(
int
j=sum/2; j>=0; j--)
{
// Find the
if
(dp[n][j] ==
true
)
{
diff = sum-2*j;
break
;
}
}
return
diff;
}
The recursive approach is to generate all possible sums from all the values of array and to check which solution is the most optimal one.
To generate sums we either include the i’th item in set 1 or don’t include, i.e., include in set 2.
To generate sums we either include the i’th item in set 1 or don’t include, i.e., include in set 2.
int
findMinRec(
int
arr[],
int
i,
int
sumCalculated,
int
sumTotal)
{
// If we have reached last element. Sum of one
// subset is sumCalculated, sum of other subset is
// sumTotal-sumCalculated. Return absolute difference
// of two sums.
if
(i==0)
return
abs
((sumTotal-sumCalculated) - sumCalculated);
// For every item arr[i], we have two choices
// (1) We do not include it first set
// (2) We include it in first set
// We return minimum of two choices
return
min(findMinRec(arr, i-1, sumCalculated+arr[i-1], sumTotal),
findMinRec(arr, i-1, sumCalculated, sumTotal));
}
// Returns minimum possible difference between sums
// of two subsets
int
findMin(
int
arr[],
int
n)
{
// Compute total sum of elements
int
sumTotal = 0;
for
(
int
i=0; i<n; i++)
sumTotal += arr[i];
// Compute result using recursive function
return
findMinRec(arr, n, 0, sumTotal);
}
Time Complexity:
All the sums can be generated by either (1) including that element in set 1. (2) without including that element in set 1. So possible combinations are :- arr[0] (1 or 2) -> 2 values arr[1] (1 or 2) -> 2 values . . . arr[n] (2 or 2) -> 2 values So time complexity will be 2*2*..... *2 (For n times), that is O(2^n).http://www.geeksforgeeks.org/dynamic-programming-set-18-partition-problem/
Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.
Examples
arr[] = {1, 5, 11, 5} Output: true The array can be partitioned as {1, 5, 5} and {11} arr[] = {1, 5, 3} Output: false The array cannot be partitioned into equal sum sets.
// 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
);
}
The problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array part[][] of size (sum/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property
part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum equal to i, otherwise false
// Returns true if arr[] can be partitioned in two subsets of
// equal sum, otherwise false
static
boolean
findPartition (
int
arr[],
int
n)
{
int
sum =
0
;
int
i, j;
// Caculcate sun of all elements
for
(i =
0
; i < n; i++)
sum += arr[i];
if
(sum%
2
!=
0
)
return
false
;
boolean
part[][]=
new
boolean
[sum/
2
+
1
][n+
1
];
// initialize top row as true
for
(i =
0
; i <= n; i++)
part[
0
][i] =
true
;
// initialize leftmost column, except part[0][0], as 0
for
(i =
1
; i <= sum/
2
; i++)
part[i][
0
] =
false
;
// Fill the partition table in botton up manner
for
(i =
1
; i <= sum/
2
; i++)
{
for
(j =
1
; j <= n; j++)
{
part[i][j] = part[i][j-
1
];
if
(i >= arr[j-
1
])
part[i][j] = part[i][j] ||
part[i - arr[j-
1
]][j-
1
];
}
}
/* // uncomment this part to print table
for (i = 0; i <= sum/2; i++)
{
for (j = 0; j <= n; j++)
printf ("%4d", part[i][j]);
printf("\n");
} */
return
part[sum/
2
][n];
}