RV
BAN USER@Backpointer - if M[N,X/2] is true, follow backpointers till u reach a null, along the trail only the cells that have current value as true are a part of solution(one of the subsets)
@2-3 - the value is false if it is out of bounds
* - as pointed out by Sanjay, this solution does splits the array into two subsets with equal sum and not average.
Solution by mapping the problem to SubSet Problem
1. Calculate the sum of all elements (num[1….N])in the array, let it be X.
2. If X is odd , no solution is possible
3. If X is even, find a subset of elements in the array whose sum is X/2.
Solution to the subset sum problem
Solution consists of filling a 2d array M[i,j]; (Dynamic Programming)where
1 <= i <= N (number of elements in the array)
1 <= j <= X/2 (desired sum)
where M[i,j] = true iff there exists a subset in the array num[1..i] whose sum is j
Fill the array using the following recursion:-
1. M[1,j] = true iff num[1] == j, for 1 <= j <= X/2
(subset sum exists, if the first element is the sum we are looking for )
2. M [i,s] = M[i-1,s] || num[i] == s || M[ i-1,s-num[i] ]
(
A subset some of s exists in array of i elements if either of the following is true :-
1. The subset sum exists in array with less than i elements
2. ith element is equal to the sum we are looking for.
3. subset with less than i elements has a subset_sum of s-num[i], in this case
num[i] provides the remaining part of the required sum
)
Once the array has been filled, M[N,X/2] determines if array can be divided into two subsets with equal sum.
The subsets can be obtained by using a backpointer with each node as follows
1. backpointer = NULL;
2-1 backpointer = num[i-1]
2-2 backpointer = NULL
2-3 backpointer = num[i-s]
to print the subset(one of the subsets),
follow backpointer till a NULL is reached
an element is part of the solution only iff the corresponding value is true
Time : O(N*X)
Space : O(N*X)
Input : files[1 ........ N]
function call : getTree(files,1)
Node getTree(files, int start)
{
if (start < files.length)
return NULL;
root = new Node(files[start])
root.left = getTree(files, start*2)
root.right = getTree(files, start*2 +1)
return root;
}
Explanation :
ith node's lc = files[2*i]
ith node's rc = files[2*i + 1]
…. so we can construct the tree recursively
- RV August 21, 2016