Introduction

Splitting an array into three parts with roughly equal sums is a partitioning problem, not just a slicing exercise. The right solution depends on what "parts" means in your case: three arbitrary groups of elements or three contiguous chunks of the original array. Those two versions have different algorithms, so it is worth defining the rule before writing code.

Start by Defining the Problem

There are two common interpretations:

• three arbitrary groups, where elements can be reassigned freely
• three contiguous sections, where the original order must be preserved

If the array is [8, 7, 6, 5, 4, 3, 2, 1], a free partition can move values anywhere. A contiguous partition can only choose two cut points. The second problem is more constrained, so it usually cannot match the balance of the first.

Because the title only says "divide an array into 3 parts," it is safer to pick one interpretation explicitly in code and in function names.

Free Partition: Greedy Heuristic

If elements can go into any of the three groups, a practical heuristic is:

1. sort values from largest to smallest
2. always place the next value into the group with the smallest current sum

This does not guarantee the mathematically optimal answer in all cases, but it is fast and usually good enough.

1from typing import List, Tuple
2
3
4def partition_into_three_groups(values: List[int]) -> List[Tuple[List[int], int]]:
5    groups = [[], [], []]
6    sums = [0, 0, 0]
7
8    for value in sorted(values, reverse=True):
9        target = min(range(3), key=lambda i: sums[i])
10        groups[target].append(value)
11        sums[target] += value
12
13    return [(groups[i], sums[i]) for i in range(3)]
14
15
16result = partition_into_three_groups([8, 7, 6, 5, 4, 3, 2, 1])
17for group, total in result:
18    print(group, total)

This approach is easy to reason about and runs quickly even for fairly large arrays. It is a heuristic because local best placement is not always globally optimal, but for "roughly equal" it is often enough.

Why the Greedy Version Works Reasonably Well

The biggest values are the hardest to place. Sorting first means the algorithm handles those early, when there is still room to balance them across the three groups.

Without sorting, a stream of small values may fill one group and leave no good place for a large value later. Greedy without descending sort is usually much worse.

The quality of the result is also easy to inspect:

1def imbalance_score(group_totals: List[int]) -> int:
2    return max(group_totals) - min(group_totals)
3
4
5totals = [total for _, total in result]
6print("imbalance:", imbalance_score(totals))

That gives a simple way to compare heuristics.

Contiguous Partition: Choose Two Cut Points

If the three parts must stay contiguous, the problem changes. One direct method is to try every pair of cut positions and keep the split with the smallest imbalance.

1from typing import List, Tuple
2
3
4def best_contiguous_three_way_split(values: List[int]) -> Tuple[Tuple[int, int], List[List[int]], List[int]]:
5    if len(values) < 3:
6        raise ValueError("Need at least three elements")
7
8    prefix = [0]
9    for value in values:
10        prefix.append(prefix[-1] + value)
11
12    best_cuts = None
13    best_parts = None
14    best_totals = None
15    best_score = float("inf")
16
17    for i in range(1, len(values) - 1):
18        for j in range(i + 1, len(values)):
19            totals = [
20                prefix[i] - prefix[0],
21                prefix[j] - prefix[i],
22                prefix[len(values)] - prefix[j],
23            ]
24            score = max(totals) - min(totals)
25
26            if score < best_score:
27                best_score = score
28                best_cuts = (i, j)
29                best_parts = [values[:i], values[i:j], values[j:]]
30                best_totals = totals
31
32    return best_cuts, best_parts, best_totals
33
34
35cuts, parts, totals = best_contiguous_three_way_split([8, 7, 6, 5, 4, 3, 2, 1])
36print(cuts)
37print(parts)
38print(totals)

This solution is exact for the contiguous version, though it is slower than the free-partition greedy approach because it tests all valid cut pairs.

Which Version Should You Use

Use the greedy free-partition version when:

• order does not matter
• you want a simple practical heuristic
• the array is large enough that exhaustive search is not attractive

Use the cut-point search when:

• parts must remain contiguous
• you need the best contiguous split
• the input size is small or moderate

Those are different problems, and treating them as the same usually leads to disappointing results.

Common Pitfalls

• Not defining whether the three parts must be contiguous or can be arbitrary groups.
• Expecting the greedy free-partition heuristic to always find the perfect optimum.
• Forgetting to sort descending before greedy assignment.
• Using a contiguous algorithm when the real problem allows free reassignment.
• Measuring only total sum and not the imbalance between the largest and smallest groups.

Summary

• "Divide into three parts" can mean either three arbitrary groups or three contiguous chunks.
• For arbitrary groups, a descending greedy assignment is a good practical heuristic.
• For contiguous chunks, two-cut search gives the best split for the chosen imbalance score.
• The right algorithm depends entirely on whether order must be preserved.
• Define the partition rule first, then optimize for that version of the problem.