Split a Set into Two with Equal Sums and Distinct Numbers

Given a list of positive integers nums, return whether you can divide the list into two groups a and b such that:

The sum of a and the sum of b are equal.
Every number in a is strictly less than every number in b.
Constraints

1 ≤ n ≤ 100,000 where n is the length of nums.
Example 1
Input
nums = [4, 9, 5]
Output
true
Explanation
We can have a = [4, 5] and b = [9] and both of their sums are 9.

Example 2
Input
nums = [9, 9]
Output
false
Explanation
We can have a = [9] and b = [9] but it doesn’t meet this criteria: “Every number in a is strictly less than every number in b.”

Set Split Algorithm

We could sort the numbers and compute the prefix sum. And then we iterate the array to see if the current prefix sum is half of the total, and also there is no same numbers in two split sets (current number is not equal to next number in the sorted array).

The complexity is O(NLogN) time due to sorting, and the space complexity is O(N) as we are using prefix sum array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool splitSum(vector<int>& nums) {
    if (nums.empty()) return false;
    sort(begin(nums), end(nums));
    int n = nums.size();
    vector<int> prefix(n, 0);
    prefix[0] = nums[0];
    for (int i = 1; i < nums.size(); ++ i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    for (int i = 0; i + 1 < n; ++ i) {
        if ((nums[i] != nums[i + 1]) && 
                (prefix[i] == prefix.back() - prefix[i])) {
            return true;
        }
    }
    return false;
}

bool splitSum(vector<int>& nums) {
    if (nums.empty()) return false;
    sort(begin(nums), end(nums));
    int n = nums.size();
    vector<int> prefix(n, 0);
    prefix[0] = nums[0];
    for (int i = 1; i < nums.size(); ++ i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    for (int i = 0; i + 1 < n; ++ i) {
        if ((nums[i] != nums[i + 1]) && 
                (prefix[i] == prefix.back() - prefix[i])) {
            return true;
        }
    }
    return false;
}

We could improve the implementation by first computing the total sum, and then updating the current running sum. Therefore, we can remove the need for the prefix sum array.

Also, when the size of the array is less than 3, it is impossible to split into two equal and distinct sets. Also, when the running sum is more than half of the total sum, we can just return false.

If the sum of all numbers in the set is an odd number, it is impossible to split into two groups with equal sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool splitSum(vector<int>& nums) {
    if (nums.size() < 3) return false;
    sort(begin(nums), end(nums));
    int sum = accumulate(begin(nums), end(nums), 0);
    if (sum & 1) {
        return false;
    }
    int running = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        running += nums[i];
        if (running * 2 == sum && (nums[i] < nums[i + 1])) {
            return true;
        }
        if (running * 2 > sum) return false;
    }
    return false;
}

bool splitSum(vector<int>& nums) {
    if (nums.size() < 3) return false;
    sort(begin(nums), end(nums));
    int sum = accumulate(begin(nums), end(nums), 0);
    if (sum & 1) {
        return false;
    }
    int running = 0;
    for (int i = 0; i + 1 < nums.size(); ++ i) {
        running += nums[i];
        if (running * 2 == sum && (nums[i] < nums[i + 1])) {
            return true;
        }
        if (running * 2 > sum) return false;
    }
    return false;
}

The time complexity is O(NLogN) although it is a bit faster. The space complexity is O(1) constant.

See also: Teaching Kids Programming – Set Split Algorithm

–EOF (The Ultimate Computing & Technology Blog)