Minimum Number of Lines to Cover Points - Solution & Explanation

Problem Overview: You receive a list of 2D points. A single straight line can cover any number of points if they are collinear. The task is to cover every point using the minimum number of lines.

The constraint is small (typically ≤10 points), which hints that exponential techniques like bit manipulation and subset dynamic programming are practical. The key challenge is efficiently determining which subsets of points lie on the same line.

Approach 1: Backtracking with Collinearity Checks (Exponential)

This approach recursively tries to draw lines through pairs of points and marks all collinear points as covered. At each step, pick an uncovered point and attempt lines formed with every other point. All points that satisfy the slope equation are included in the same line. Continue recursively until all points are covered.

The algorithm repeatedly checks whether three points are collinear using the cross-product condition. While straightforward, it recomputes many states and explores redundant configurations. Time complexity grows roughly O(n! * n) in the worst case with O(n) space for recursion, making it impractical without pruning.

Approach 2: Precompute Lines + Bitmask Dynamic Programming (Optimal)

This approach models the problem as covering a set of points using the minimum number of line subsets. Represent the set of points with a bitmask where bit i indicates whether point i is covered. For every pair of points, compute a mask containing all points that lie on the same line using a geometry collinearity test.

Once these line masks are prepared, apply DP over subsets. Let dp[mask] represent the minimum number of lines required to cover the points represented by mask. For each state, pick the first uncovered point and try every precomputed line passing through it. Transition to a new mask by marking all points on that line as covered.

This reduces the search space dramatically because each line operation covers multiple points at once. Precomputation takes O(n^3) time, and the DP over subsets takes about O(n^2 * 2^n) time with O(2^n) space. The method combines dynamic programming, bitmasking, and basic geometry concepts.

Recommended for interviews: The bitmask DP approach is what interviewers expect. Starting with the brute-force backtracking explanation shows you understand the search space. Transitioning to subset DP with precomputed collinear masks demonstrates strong optimization skills and familiarity with small-constraint exponential problems.