# Number of Sets of K Non-Overlapping Line Segments
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments)
Canonical: https://scaleengineer.com/dsa/problems/number-of-sets-of-k-non-overlapping-line-segments
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
Given `n` points on a 1-D plane, where the `ith` point (from `0` to `n-1`) is at `x = i`, find the number of ways we can draw **exactly** `k` **non-overlapping** line segments such that each segment covers two or more points. The endpoints of each segment must have **integral coordinates**. The `k` line segments **do not** have to cover all `n` points, and they are **allowed** to share endpoints.

Return _the number of ways we can draw_ `k` _non-overlapping line segments_ _._ Since this number can be huge, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-sets-of-k-non-overlapping-line-segments/image0.png) 

**Input:** n = 4, k = 2
**Output:** 5
**Explanation:** The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

**Example 2:**

**Input:** n = 3, k = 1
**Output:** 3
**Explanation:** The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

**Example 3:**

**Input:** n = 30, k = 7
**Output:** 796297179
**Explanation:** The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.

**Constraints:**

* `2 <= n <= 1000`
* `1 <= k <= n-1`

# Approaches
## Naive Dynamic Programming
This approach uses a straightforward dynamic programming solution. We build the solution incrementally by considering one point at a time. The state of our DP, `dp[i][j]`, represents the number of ways to form `j` segments using the first `i` points. The transition involves a summation over all possible start points for a new segment ending at the current point, which leads to a cubic time complexity.
**Time:** O(n^2 * k). The three nested loops for `i` (up to `n`), `j` (up to `k`), and `p` (up to `n`) result in a cubic time complexity. · **Space:** O(n * k) to store the 2D DP table.
**Pros:** Conceptually simple and directly follows the problem's recursive structure.
**Cons:** Very high time complexity, which will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
Let `dp[i][j]` be the number of ways to place `j` non-overlapping segments using the first `i` points (i.e., points `0, 1, ..., i-1`).

To compute `dp[i][j]`, we consider two cases for the `i`-th point (coordinate `i-1`):
1.  **Point `i-1` is not used as an endpoint**: In this case, all `j` segments must be formed using the first `i-1` points (`0, ..., i-2`). The number of ways for this is simply `dp[i-1][j]`.
2.  **Point `i-1` is the right endpoint of a new segment**: This new segment must be the `j`-th segment. Let's say it is `[p, i-1]`, where `0 <= p < i-1`. The remaining `j-1` segments must be formed using points `0, ..., p`. The number of ways to do this is `dp[p+1][j-1]`. Since `p` can be any point from `0` to `i-2`, we must sum the ways for all possible start points.

This logic gives us the recurrence relation:
`dp[i][j] = dp[i-1][j] + sum_{p=0}^{i-2} dp[p+1][j-1]`

The base cases are `dp[i][0] = 1` for all `i >= 1` (one way to place zero segments) and `dp[0][j] = 0` for `j > 0`. The final answer is `dp[n][k]`.

The implementation requires three nested loops: one for `i` (from 1 to `n`), one for `j` (from 1 to `k`), and an inner loop for the summation over `p` (from 0 to `i-2`).

```java
class Solution {
    public int numberOfSets(int n, int k) {
        int MOD = 1_000_000_007;
        long[][] dp = new long[n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                // Case 1: Point i-1 is not used
                dp[i][j] = dp[i - 1][j];
                
                // Case 2: Point i-1 is the right endpoint of the j-th segment
                for (int p = 0; p < i - 1; p++) {
                    // Segment is [p, i-1]. j-1 segments must be placed using points 0..p
                    // which means using p+1 points.
                    dp[i][j] = (dp[i][j] + dp[p + 1][j - 1]) % MOD;
                }
            }
        }
        return (int) dp[n][k];
    }
}
```
### Algorithm
- Create a 2D DP table `dp[n+1][k+1]` to store the number of ways.
- `dp[i][j]` will store the number of ways to place `j` segments using the first `i` points (from `0` to `i-1`).
- Initialize the base cases: `dp[i][0] = 1` for all `i`, as there's one way to place zero segments (by doing nothing).
- Iterate through the points `i` from 1 to `n`.
- For each `i`, iterate through the number of segments `j` from 1 to `k`.
- The value of `dp[i][j]` is calculated based on two possibilities for point `i-1`:
  1. Point `i-1` is not used as an endpoint. The number of ways is `dp[i-1][j]`.
  2. Point `i-1` is the right endpoint of the `j`-th segment. This segment can be `[p, i-1]` for any `0 <= p < i-1`. The previous `j-1` segments must be placed using points `0` to `p`. The number of ways for this is `dp[p+1][j-1]`. We sum this over all possible `p`.
- The recurrence is: `dp[i][j] = dp[i-1][j] + sum_{p=0}^{i-2} dp[p+1][j-1]`.
- The final answer is `dp[n][k]`.

## Optimized Dynamic Programming
This approach improves upon the naive DP by optimizing the recurrence relation. The inner loop, which calculates a summation, can be eliminated by observing the relationship between `dp[i][j]` and `dp[i-1][j]`. This mathematical trick allows us to compute each DP state in constant time, reducing the overall time complexity from cubic to quadratic.
**Time:** O(n * k). We iterate through the `n x k` DP table, and each state is computed in O(1) time. · **Space:** O(n * k) for the DP table. This can be optimized to O(k) by noticing that `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, so we only need to store the two previous rows.
**Pros:** Significantly more efficient than the naive DP approach.; Passes the time limits for the given constraints.
**Cons:** The derivation of the recurrence is less intuitive.; Requires careful handling of indices and modular arithmetic to avoid errors.
### Explanation
We start with the same recurrence as the naive approach:
`dp[i][j] = dp[i-1][j] + sum_{q=1}^{i-1} dp[q][j-1]`

Let's analyze the summation part. We can express `dp[i-1][j]` similarly:
`dp[i-1][j] = dp[i-2][j] + sum_{q=1}^{i-2} dp[q][j-1]`

Notice that `sum_{q=1}^{i-1} dp[q][j-1] = sum_{q=1}^{i-2} dp[q][j-1] + dp[i-1][j-1]`.

By subtracting the second recurrence from the first, we get:
`dp[i][j] - dp[i-1][j] = (dp[i-1][j] - dp[i-2][j]) + dp[i-1][j-1]`

Rearranging the terms gives us a new, more efficient recurrence that doesn't involve a summation:
`dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1]`

Using this recurrence, each state `dp[i][j]` can be computed in `O(1)` time. We still need to fill an `n x k` table, so the total time complexity becomes `O(n * k)`. When implementing, we must be careful with modular arithmetic, especially subtraction, by adding `MOD` before taking the modulus to handle potential negative results.

```java
class Solution {
    public int numberOfSets(int n, int k) {
        int MOD = 1_000_000_007;
        long[][] dp = new long[n + 1][k + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                // dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1]
                long val = (2 * dp[i - 1][j]) % MOD;
                val = (val - dp[i - 2][j] + MOD) % MOD; // Add MOD to handle negative results
                val = (val + dp[i - 1][j - 1]) % MOD;
                dp[i][j] = val;
            }
        }
        return (int) dp[n][k];
    }
}
```
This approach is efficient enough to pass within the given constraints.
### Algorithm
- The recurrence from the naive approach is `dp[i][j] = dp[i-1][j] + sum_{q=1}^{i-1} dp[q][j-1]`.
- Observe that the summation term can be eliminated. Write the recurrence for `dp[i-1][j]`: `dp[i-1][j] = dp[i-2][j] + sum_{q=1}^{i-2} dp[q][j-1]`.
- Subtract the second equation from the first: `dp[i][j] - dp[i-1][j] = (dp[i-1][j] - dp[i-2][j]) + dp[i-1][j-1]`.
- Rearrange to get the optimized recurrence: `dp[i][j] = 2 * dp[i-1][j] - dp[i-2][j] + dp[i-1][j-1]`.
- Create a 2D DP table `dp[n+1][k+1]` and initialize base cases `dp[i][0] = 1`.
- Iterate `i` from 2 to `n` and `j` from 1 to `k`, filling the table using the new recurrence.
- Return `dp[n][k]`.

## Combinatorial Approach
The most efficient solution involves reframing the problem from a dynamic programming perspective to a combinatorial one. The problem of choosing `k` non-overlapping line segments can be mapped to a problem of choosing `2k` numbers from a specific range. This transformation, a variant of the 'stars and bars' method, leads to a direct mathematical formula for the answer, which can be computed very efficiently.
**Time:** O(n + k + log(MOD)). The dominant part is the precomputation of factorials, which takes O(n+k). The modular inverse calculation takes O(log(MOD)). After precomputation, the answer is found in O(1). · **Space:** O(n + k) to store the precomputed factorials and inverse factorials.
**Pros:** Extremely efficient, with a time complexity that is linear in `n+k` for precomputation.; Provides a direct, closed-form solution.; Elegant mathematical approach.
**Cons:** The combinatorial insight (stars and bars transformation) can be difficult to derive.; Requires knowledge of modular arithmetic, including combinations and modular multiplicative inverse.
### Explanation
Let the `k` non-overlapping segments be `[s_1, e_1], [s_2, e_2], ..., [s_k, e_k]`. By the problem definition, we can order them such that:
`0 <= s_1 < e_1 <= s_2 < e_2 <= ... <= s_k < e_k <= n-1`

This is a sequence of `2k` integers with a mix of strict (`<`) and non-strict (`<=`) inequalities. We can convert this into a problem of choosing `2k` distinct integers by applying a transformation. Let's define a new sequence `z_1, z_2, ..., z_{2k}` as follows:
- `z_1 = s_1`
- `z_2 = e_1`
- `z_3 = s_2 + 1`
- `z_4 = e_2 + 1`
- ...
- `z_{2i-1} = s_i + i - 1`
- `z_{2i} = e_i + i - 1`

This transformation cleverly converts the original sequence into a strictly increasing sequence: `0 <= z_1 < z_2 < ... < z_{2k}`.

The upper bound for `z_{2k}` is `e_k + k - 1`. Since `e_k <= n-1`, we have `z_{2k} <= (n-1) + (k-1) = n+k-2`.

So, the problem is now equivalent to choosing `2k` distinct numbers from the range `[0, n+k-2]`. The total count of numbers in this range is `(n+k-2) - 0 + 1 = n+k-1`.

The number of ways to choose `2k` distinct numbers from `n+k-1` numbers is given by the binomial coefficient `C(n+k-1, 2k)`.

We can compute `C(N, K) = N! / (K! * (N-K)!)` modulo `10^9 + 7`. Since `10^9 + 7` is a prime number, we can precompute factorials and their modular inverses (using Fermat's Little Theorem) to find the answer efficiently.

```java
class Solution {
    public int numberOfSets(int n, int k) {
        int MOD = 1_000_000_007;
        int N = n + k - 1;
        int K = 2 * k;
        
        if (K > N) {
            return 0;
        }

        // Calculate C(N, K) % MOD
        long[] fact = new long[N + 1];
        long[] invFact = new long[N + 1];
        fact[0] = 1;
        invFact[0] = 1;

        for (int i = 1; i <= N; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        invFact[N] = power(fact[N], MOD - 2, MOD);
        for (int i = N - 1; i >= 1; i--) {
            invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
        }

        long numerator = fact[N];
        long denominator = (invFact[K] * invFact[N - K]) % MOD;
        
        return (int) ((numerator * denominator) % MOD);
    }

    private long power(long base, long exp, int mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- Realize the problem is equivalent to a combinatorial selection problem.
- The condition `0 <= s_1 < e_1 <= s_2 < ... <= s_k < e_k <= n-1` can be transformed into a strictly increasing sequence `0 <= z_1 < z_2 < ... < z_{2k} <= n+k-2`.
- This is equivalent to choosing `2k` distinct numbers from the set `{0, 1, ..., n+k-2}`, which has `n+k-1` elements.
- The number of ways is given by the binomial coefficient `C(n+k-1, 2k)`.
- To compute `C(N, K) mod P` where `P` is prime, we use the formula `(N! * inv(K!) * inv((N-K)!)) mod P`.
- Precompute factorials and their modular inverses up to `n+k-1`.
- Calculate the final result using the precomputed values.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int numberOfSets(int n, int k) {
    int[][] f = new int[n + 1][k + 1];
    int[][] g = new int[n + 1][k + 1];
    f[1][0] = 1;
    for (int i = 2; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) {
        f[i][j] = (f[i - 1][j] + g[i - 1][j]) % MOD;
        g[i][j] = g[i - 1][j];
        if (j > 0) {
          g[i][j] += f[i - 1][j - 1];
          g[i][j] %= MOD;
          g[i][j] += g[i - 1][j - 1];
          g[i][j] %= MOD;
        }
      }
    }
    return (f[n][k] + g[n][k]) % MOD;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int f[1010][1010];
  int g[1010][1010];
  const int mod = 1e9 + 7;
  int numberOfSets(int n, int k) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    f[1][0] = 1;
    for (int i = 2; i <= n; ++i) {
      for (int j = 0; j <= k; ++j) {
        f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod;
        g[i][j] = g[i - 1][j];
        if (j > 0) {
          g[i][j] += f[i - 1][j - 1];
          g[i][j] %= mod;
          g[i][j] += g[i - 1][j - 1];
          g[i][j] %= mod;
        }
      }
    }
    return (f[n][k] + g[n][k]) % mod;
  }
};

```

### Python

```python
class Solution:
    def numberOfSets(self, n: int, k: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (k + 1) for _ in range(n + 1)] g = [[0] * (k + 1) for _ in range(n + 1)] f[1][0] = 1 for i in range(2, n + 1): for j in range(k + 1): f[i][j] = (f[i - 1][j] + g[i - 1][j]) % mod g[i][j] = g[i - 1][j] if j: g[i][j] += f[i - 1][j - 1] g[i][j] %= mod g[i][j] += g[i - 1][j - 1] g[i][j] %= mod return (f[- 1][- 1] + g[- 1][- 1]) % mod

```