Abstract / Summary

Count the ways to choose k non overlapping line segments from a list of segments.

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 46% (30k+ submissions).

Typical patterns to solve this problem:

• Combinatorics
• Dynamic Programming
• Math
• Prefix Sum

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 single public method numberOfSets. The method computes the number of ways to choose k non-empty, pairwise disjoint segments from a set of n ordered points, where each segment must contain at least one point. The result is returned modulo 1 000 000 007. The core of the algorithm is a depth-first recursion with memoization, encapsulated in the nested function deeper. The recursion explores two mutually exclusive choices at each step: either to close the current segment (if one is open) or to start/continue a segment, while also handling the possibility of skipping a point when no segment is open.

Core Logic

The entry point numberOfSets simply forwards the parameters n and k to the memoized helper:

return deeper(n, k)

The helper deeper is defined with three parameters:

• points - the number of remaining points that can be considered.
• segments - the number of segments that still need to be placed.
• inside - a boolean flag indicating whether the recursion is currently inside an open segment.

The recursion terminates early in two situations. When there are no points left (points == 0) the function returns 0 because a segment cannot be completed without points. When there are no segments left to place (segments == 0) the function returns 1, representing a single valid configuration (all required segments have already been formed).

The body of the recursion distinguishes two states based on inside:

When inside is true, the algorithm is inside an open segment. Two possibilities are explored:

• Closing the current segment at the current point, which consumes one segment but does not consume a point:

  one = deeper(points, segments - 1, False)

• Extending the current segment by including the current point, which consumes a point but leaves the segment open:

  two = deeper(points - 1, segments, True)

When inside is false, the algorithm is not inside a segment. Again two possibilities are considered:

• Skipping the current point entirely, which consumes a point and leaves the state unchanged:

  one = deeper(points - 1, segments, False)

• Starting a new segment that includes the current point, which consumes a point and opens a segment:

  two = deeper(points - 1, segments, True)

Both branches compute the same two transition, reflecting that the act of starting a segment and immediately placing a point is identical regardless of the previous state. The results of the two branches are summed and reduced modulo the large prime:

return (one + two) % 1_000_000_007

The @lru_cache(maxsize = 200_000) decorator memoizes each distinct combination of (points, segments, inside). This eliminates redundant recomputation and ensures that each sub-problem is solved at most once.

Edge Cases Handled

The base conditions explicitly address scenarios where the recursion would otherwise continue indefinitely. When points reaches zero, the function returns 0, correctly handling the case where there are insufficient points to complete any remaining segment. When segments reaches zero, the function returns 1, capturing the situation where all required segments have already been placed, regardless of any leftover points. The boolean flag inside guarantees that a segment cannot be closed without having been opened first, preventing invalid configurations where a segment ends before it starts. The modulo operation guarantees that intermediate sums never overflow the integer range, preserving correctness for large inputs.

Performance Optimizations

Memoization via lru_cache is the primary optimization. By caching results for each triple (points, segments, inside), the algorithm reduces the exponential branching factor of the naïve recursion to a polynomial number of distinct states. The cache size limit of 200 000 entries is sufficient for typical problem constraints and prevents unbounded memory growth. The modulo reduction is performed at each return, keeping intermediate values bounded and avoiding the cost of large integer arithmetic. The use of a nested function keeps the cache localized to a single invocation of numberOfSets, ensuring that repeated calls to the method start with a fresh cache, which is appropriate for isolated test cases. The recursion avoids unnecessary parameters by reusing the same variable names for both branches, reducing the overhead of argument passing. Overall, the combination of early termination, state flagging, and memoization yields an efficient solution for the combinatorial counting problem.

Imagine you have a long row of dots on a piece of paper, and you want to use a magic marker to draw lines connecting some of them to make little groups. The goal is to figure out how many different ways you can pick spots to draw these lines so that you end up with exactly the number of groups you wanted.

This code acts like a tiny robot that looks at the dots one by one from left to right. When the robot looks at a dot, it has to make a choice. It can decide to skip the dot and move to the next one, or it can start a new line segment if it is allowed to. If it is already drawing a line, it can decide to finish that line at the current dot or keep the line going to the next dot.

The robot keeps track of three things as it works. It remembers how many dots are left to look at, how many more segments it still needs to finish building, and whether it is currently in the middle of drawing a segment or not. Because there are so many dots, the robot uses a smart trick to write down the answers it has already found on a notepad. If it runs into the same situation again, it just checks the notepad instead of doing the work all over again. By exploring all these choices, the robot counts up all the combinations and gives the final answer.

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

Time: polynomial
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	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

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