Abstract / Summary

Check if an array can be split into two nonempty groups with equal sums and the same count of odd numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method validPartition that determines whether a list of integers can be split into contiguous sub-arrays that each satisfy one of three specific patterns. The method uses a depth-first search with memoization to explore possible partitions from the start of the list to the end. A recursion limit is increased to accommodate deep call stacks for long inputs.

Key Steps

Input preparation and recursion setup

size = len(nums)

@cache
def deeper(pos):
    ...
sys.setrecursionlimit(100_100)
return deeper(0)

The length of the input list is stored in size. A nested function deeper is defined and decorated with @cache, which automatically memoizes results for each starting position pos. The recursion limit is raised to a value larger than typical defaults, ensuring that the interpreter can handle the maximum possible recursion depth for the problem constraints. The algorithm begins by invoking deeper with the initial position 0.

Base case - successful partition

if pos == size:
    return True

When the current index reaches the length of the list, all elements have been successfully grouped into valid sub-arrays, and the function returns True.

Base case - insufficient elements

if pos == size - 1:
    return False

If only a single element remains, it cannot form any of the allowed groups (which require at least two elements). The function therefore returns False.

Attempt to form a pair of equal numbers

if nums[pos] == nums[pos + 1]:
    if deeper(pos + 2):
        return True
if pos == size - 2:
    return False

When the current element matches the next one, the code tries to treat the two as a valid pair. It recursively checks the remainder starting at pos + 2. If that recursive call succeeds, the current call returns True. If the list ends after exactly two elements (pos == size - 2) and the pair condition was not satisfied, the function returns False because no further grouping is possible.

Attempt to form a triple of equal numbers

if nums[pos] == nums[pos + 1] == nums[pos + 2] and deeper(pos + 3):
    return True

If three consecutive elements are identical, they satisfy the “three equal numbers” rule. The function proceeds recursively from pos + 3. A successful recursive result leads to an immediate True.

Attempt to form a consecutive increasing triple

if nums[pos] == nums[pos + 1] - 1 == nums[pos + 2] - 2 and deeper(pos + 3):
    return True

This condition checks whether the three numbers form a strictly increasing sequence with a difference of one between each adjacent pair (e.g., [4,5,6]). If the pattern holds, the recursion continues from pos + 3. A successful continuation yields True.

Fallback when no pattern matches

return False

If none of the above patterns can be applied at the current position, the function concludes that a valid partition is impossible from this state and returns False.

Edge Cases Handled

The algorithm explicitly addresses several boundary conditions:

• An empty list (size == 0) triggers the base case pos == size on the first call, returning True because no elements trivially satisfy the partition requirement.
• A single-element list (size == 1) reaches the pos == size - 1 check and returns False, reflecting the impossibility of forming a valid group.
• A two-element list where the elements are equal satisfies the pair condition, leading to a recursive call with pos == size and a final True. If the two elements differ, the pos == size - 2 guard returns False.
• A three-element list is examined for both the “three equal” and “consecutive increasing” patterns. If either pattern matches, the recursion advances to pos == size, yielding True. If neither matches, the function falls through to the final False.
• For longer lists, the code ensures that attempts to access nums[pos + 1] or nums[pos + 2] are guarded by earlier length checks, preventing out-of-range errors.

Performance Optimizations

The most significant optimization is the use of the @cache decorator on the recursive helper deeper. By storing the boolean result for each distinct starting index, the algorithm avoids recomputing the same sub-problem multiple times. This memoization transforms the exponential blow-up typical of naïve recursive backtracking into a linear number of distinct states, each evaluated at most once.

Increasing the recursion limit with sys.setrecursionlimit(100_100) prevents premature termination for inputs that require deep recursion, allowing the algorithm to fully explore the state space without incurring additional overhead from exception handling.

The early returns after each successful pattern check (return True) short-circuit further unnecessary evaluations at the current depth, ensuring that the function proceeds only along viable paths.

Collectively, these techniques enable the solution to handle large inputs efficiently while maintaining a clear and concise recursive structure.

Imagine a long train made of many colorful blocks sitting in a row. The goal is to see if we can group every single block into valid pairs or special little squads of three.

The computer starts at the very beginning of the train. It looks at the first few blocks and tries to figure out how to arrange them. If it finds two blocks that are the same color, it sets them aside as a pair and checks if the leftover blocks in the back of the train can also be grouped properly. If it finds three blocks that are all the same color, or three blocks that go up by one like one, two, and three, it sets those aside as a group of three and checks the rest of the train too.

Whenever the computer hits a spot where it cannot make a pair or a group of three, it stops and goes back a step to try a different way. It keeps doing this over and over again, bouncing back and forth through the train until it either finds a way to group every single block or runs out of options. If it makes it all the way to the end of the train with every block organized, it means the train is perfectly sorted.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Python	Java	C++		TS
	WalkCCC		Python	Java	C++
	leetcode.ca		Python	Java	C++	Go	TS
	Progiez		Python	Java	C++
github	charles-wangkai			Java
	everthis	JS
	fsq				C++
	JoshCrozier	JS
	lkwq007		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality