Hi,
I've solved it, but not able to solved with complexity lower than O(nlog N)m, because of sorting. Maybe somedy smarter than me show me better solution.
Given a set of integers (which may include repeated integers), determine if there's a way to split the set into two subsets
A and B such that the sum of the integers in both sets is the same, and all of the integers in A are strictly smaller than all of the integers in B.
Note: Strictly smaller denotes that every integer in A must be less than, and not equal to, every integer in B.
Signature
bool balancedSplitExists(int[] arr)
Input
All integers in array are in the range [0, 1,000,000,000].
Output
Return true if such a split is possible, and false otherwise.
*Example 1
arr = [1, 5, 7, 1]
output = true
We can split the set into A = {1, 1, 5} and B = {7}.
*
Example 2
arr = [12, 7, 6, 7, 6]
output = false
We can't split the set into A = {6, 6, 7} and B = {7, 12} since this doesn't satisfy the requirement that all
integers in A are smaller than all integers in B.*
func balancedSplitExists(arr []int) bool {
var leftSum, rightSum int
sort.Ints(arr)
for i:=0; i < len(arr); i++ {
leftSum += arr[i]
}
for i:=len(arr)-1; i >= 0;i-- {
leftSum -= arr[i]
rightSum += arr[i]
if leftSum == rightSum {
if arr[i-1] < arr[i] {
return true
}
}
}
return false
}Unit Test
func Test_Partition_Equal_Subset_Sum(t *testing.T) {
testDatas := []struct{
nums []int
result bool
} {
{ []int{1, 5, 7, 1}, true},
{ []int{12, 7, 6, 7, 6}, false},
{ []int{}, false},
{ []int{ 2,}, false},
{ []int{20, 2,}, false},
{ []int{5,7,20,12,5,7,6,14,5,5,6,}, true},
{ []int{5,7,20,12,5,7,6,7,14,5,5,6,}, false},
{ []int{1,1,1,1,1,1,1,1,1,1,1,1,}, false},
}
for _, td := range testDatas {
r := balancedSplitExists(td.nums)
if r != td.result {
t.Errorf("Source: %d n Expected:%v \n Actual: %v\n",
td.nums,
td.result,
r)
}
}
}