# Split With Minimum Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/split-with-minimum-sum)
Canonical: https://scaleengineer.com/dsa/problems/split-with-minimum-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
---
## Problem
Given a positive integer `num`, split it into two non-negative integers `num1` and `num2` such that:

* The concatenation of `num1` and `num2` is a permutation of `num`.  
  * In other words, the sum of the number of occurrences of each digit in `num1` and `num2` is equal to the number of occurrences of that digit in `num`.
* `num1` and `num2` can contain leading zeros.

Return _the **minimum** possible sum of_ `num1` _and_ `num2`.

**Notes:**

* It is guaranteed that `num` does not contain any leading zeros.
* The order of occurrence of the digits in `num1` and `num2` may differ from the order of occurrence of `num`.

**Example 1:**

**Input:** num = 4325
**Output:** 59
**Explanation:** We can split 4325 so that `num1` is 24 and `num2` is 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

**Example 2:**

**Input:** num = 687
**Output:** 75
**Explanation:** We can split 687 so that `num1` is 68 and `num2` is 7, which would give an optimal sum of 75.

**Constraints:**

* `10 <= num <= 109`

# Approaches
## Brute Force with Subset Partitioning
This approach systematically explores every possible way to divide the digits of the input number `num` into two separate groups. For each possible division (or partition), it constructs the two smallest possible numbers, `num1` and `num2`, by arranging the digits in each group in ascending order. It then calculates their sum and keeps track of the minimum sum found across all partitions. While exhaustive and guaranteed to be correct, this method is computationally more intensive than the optimal greedy solution.
**Time:** O(2^k * k log k), where `k` is the number of digits in `num`. For each of the `2^k` ways to partition the digits, we sort the two resulting sub-lists. Since `k <= 10`, this is acceptable. · **Space:** O(k) for the recursion depth and to store the lists of digits, where `k` is the number of digits.
**Pros:** It is a correct approach as it exhaustively checks all valid splits of the digits.; It serves as a good baseline to verify the correctness of more optimized solutions.
**Cons:** The time complexity is exponential, making it inefficient for larger numbers of digits (though feasible for this problem's constraints).; The implementation is significantly more complex than the greedy approach due to recursion and backtracking.
### Explanation
The core idea is to treat the problem as finding the best partition of a set of digits. We can use a recursive backtracking algorithm to generate all possible partitions.

For an input number like `4325`, the digits are `{4, 3, 2, 5}`. The algorithm will explore partitions like:
- `{4}` and `{3, 2, 5}` -> `num1=4`, `num2=235`, sum=`239`
- `{4, 3}` and `{2, 5}` -> `num1=34`, `num2=25`, sum=`59`
- ... and so on for all `2^(k-1) - 1` non-trivial partitions.

For each partition, we form the smallest numbers possible. If a partition for `num1` is `{5, 2}`, the smallest number we can form is `25`. This is done by sorting the digits within each partition. The algorithm maintains a global minimum, updating it whenever a smaller sum is found.

Here is a code snippet demonstrating the recursive partitioning:
```java
import java.util.*;

class Solution {
    long minSum = Long.MAX_VALUE;

    public int splitNum(int num) {
        String s = Integer.toString(num);
        List<Character> digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            digits.add(c);
        }
        
        // Start the recursive partitioning from the first digit.
        generatePartitions(0, digits, new ArrayList<>(), new ArrayList<>());
        return (int) minSum;
    }

    private void generatePartitions(int index, List<Character> allDigits, List<Character> list1, List<Character> list2) {
        // Base case: all digits have been assigned.
        if (index == allDigits.size()) {
            // Ensure both numbers are non-empty as per the problem's implicit split.
            if (!list1.isEmpty() && !list2.isEmpty()) {
                long num1 = buildSmallestNumber(list1);
                long num2 = buildSmallestNumber(list2);
                minSum = Math.min(minSum, num1 + num2);
            }
            return;
        }

        char currentDigit = allDigits.get(index);

        // Option 1: Add the current digit to the first number's list.
        list1.add(currentDigit);
        generatePartitions(index + 1, allDigits, list1, list2);
        list1.remove(list1.size() - 1); // Backtrack to explore other possibilities.

        // Option 2: Add the current digit to the second number's list.
        list2.add(currentDigit);
        generatePartitions(index + 1, allDigits, list1, list2);
        list2.remove(list2.size() - 1); // Backtrack.
    }

    // Helper function to build the smallest number from a list of digits.
    private long buildSmallestNumber(List<Character> digitList) {
        Collections.sort(digitList);
        StringBuilder sb = new StringBuilder();
        for (char c : digitList) {
            sb.append(c);
        }
        return Long.parseLong(sb.toString());
    }
}
```
### Algorithm
- 1. Extract the digits of the input `num` into a list.
- 2. Implement a recursive function `generatePartitions` that takes the current digit's index and the lists for `num1` and `num2`.
- 3. In the recursive function, for each digit, explore two branches: adding it to `list1` or adding it to `list2`.
- 4. The base case for the recursion is when all digits have been assigned. At this point, check if both lists are non-empty.
- 5. If they are, build the smallest possible numbers from `list1` and `list2` by sorting their digits and concatenating them.
- 6. Calculate the sum of these two numbers and update a global minimum sum.
- 7. After the recursion completes, the global minimum sum is the result.

## Greedy Sorting Approach
This is the most efficient and elegant solution. The core insight is that to minimize the sum `num1 + num2`, we should construct `num1` and `num2` to be as small as possible. A number's magnitude is primarily determined by its most significant digits and its length. By sorting all available digits and then distributing them one by one, alternating between `num1` and `num2`, we achieve two things:
1. The smallest digits (`d1`, `d2`) are placed in the most significant positions of `num1` and `num2`.
2. The lengths of `num1` and `num2` are kept as balanced as possible (differing by at most one).
This greedy strategy correctly yields the minimum possible sum.
**Time:** O(k log k), where `k` is the number of digits in `num`. The dominant operation is sorting the `k` digits. Since `k` is small (at most 10), this is very fast. · **Space:** O(k) to store the character array for the digits, where `k` is the number of digits.
**Pros:** Extremely efficient with a near-linear time complexity.; Simple and concise to implement.; Directly solves the problem without unnecessary exploration of non-optimal solutions.
**Cons:** The correctness of the greedy choice is not immediately obvious and relies on the insight about minimizing numbers by placing small digits in high-value places.
### Explanation
Let's walk through an example: `num = 4325`.

1. **Extract and Sort Digits**: The digits are `4, 3, 2, 5`. Sorting them gives `2, 3, 4, 5`.
2. **Distribute Alternately**: We build two new numbers, `num1` and `num2`.
   - The first smallest digit, `2`, goes to `num1`. (`num1` = "2")
   - The second smallest digit, `3`, goes to `num2`. (`num2` = "3")
   - The third smallest digit, `4`, goes to `num1`. (`num1` = "24")
   - The fourth smallest digit, `5`, goes to `num2`. (`num2` = "35")
3. **Calculate Sum**: We have `num1 = 24` and `num2 = 35`. Their sum is `24 + 35 = 59`.

This process guarantees that the smallest digits contribute to the higher place values (tens, hundreds, etc.), thus minimizing the overall sum. The implementation is straightforward.

Here is the Java code for this approach:
```java
import java.util.Arrays;

class Solution {
    public int splitNum(int num) {
        // Convert the number to a character array to easily access and sort digits.
        char[] digits = Integer.toString(num).toCharArray();
        
        // Sort the digits in ascending order.
        Arrays.sort(digits);
        
        // Initialize two string builders to construct the two new numbers.
        StringBuilder num1Str = new StringBuilder();
        StringBuilder num2Str = new StringBuilder();
        
        // Iterate through the sorted digits and distribute them alternately.
        for (int i = 0; i < digits.length; i++) {
            if (i % 2 == 0) {
                // Even-indexed digits (0, 2, ...) go to the first number.
                num1Str.append(digits[i]);
            } else {
                // Odd-indexed digits (1, 3, ...) go to the second number.
                num2Str.append(digits[i]);
            }
        }
        
        // Convert the resulting strings to integers.
        int num1 = Integer.parseInt(num1Str.toString());
        int num2 = Integer.parseInt(num2Str.toString());
        
        // Return the sum.
        return num1 + num2;
    }
}
```
### Algorithm
- 1. Convert the input integer `num` to a string, then to a character array.
- 2. Sort the character array in ascending order.
- 3. Initialize two string builders, `s1` and `s2`.
- 4. Loop through the sorted character array from `i = 0` to `length - 1`.
- 5. If `i` is an even index, append the digit `digits[i]` to `s1`.
- 6. If `i` is an odd index, append the digit `digits[i]` to `s2`.
- 7. After the loop, convert `s1` and `s2` to integers.
- 8. Return the sum of the two integers.

# Solutions
### Java

```java
class Solution {
public
  int splitNum(int num) {
    int[] cnt = new int[10];
    int n = 0;
    for (; num > 0; num /= 10) {
      ++cnt[num % 10];
      ++n;
    }
    int[] ans = new int[2];
    for (int i = 0, j = 0; i < n; ++i) {
      while (cnt[j] == 0) {
        ++j;
      }
      --cnt[j];
      ans[i & 1] = ans[i & 1] * 10 + j;
    }
    return ans[0] + ans[1];
  }
}

```

### Python

```python
class Solution:
    def splitNum(self, num: int) -> int: cnt = Counter() n = 0 while num: cnt[num % 10] += 1 num //= 10 n += 1 ans = [0] * 2 j = 0 for i in range(n): while cnt[j] == 0: j += 1 cnt[j] -= 1 ans[i & 1] = ans[i & 1] * 10 + j return sum(ans)

```

### CPP

```cpp
class Solution {
public:
  int splitNum(int num) {
    int cnt[10]{};
    int n = 0;
    for (; num; num /= 10) {
      ++cnt[num % 10];
      ++n;
    }
    int ans[2]{};
    for (int i = 0, j = 0; i < n; ++i) {
      while (cnt[j] == 0) {
        ++j;
      }
      --cnt[j];
      ans[i & 1] = ans[i & 1] * 10 + j;
    }
    return ans[0] + ans[1];
  }
};

```