Number of sets of k non overlapping line segments

Math Dynamic Programming Combinatorics Prefix Sum

45.6% acceptance

Feb 25, 2026

489

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

const MOD: i64 = 1_000_000_007;

impl Solution {
  pub fn number_of_sets(n: i32, k: i32) -> i32 {
    // Answer = C(n+k-1, 2k) mod MOD
    let top = (n + k - 1) as usize;
    let bot = (2 * k) as usize;
    // Precompute factorials up to top
    let mut fact = vec![1i64; top + 1];
    for i in 1..=top { fact[i] = fact[i-1] * i as i64 % MOD; }
    let mut inv_fact = vec![1i64; top + 1];
    inv_fact[top] = Self::pow_mod(fact[top], MOD - 2, MOD);
    for i in (0..top).rev() { inv_fact[i] = inv_fact[i+1] * (i+1) as i64 % MOD; }
    (fact[top] * inv_fact[bot] % MOD * inv_fact[top - bot] % MOD) as i32
  }

  fn pow_mod(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
    let mut result = 1i64;
    base %= modulus;
    while exp > 0 {
      if exp & 1 == 1 { result = result * base % modulus; }
      exp >>= 1;
      base = base * base % modulus;
    }
    result
  }
}