NeetCode #695LC-368Medium1-D Dynamic Programming
← Back to All Problems#695 · #368 · Largest Divisible Subset(最大整除子集)
📌 Problem Statement & Constraints
Given a set of distinct positive integers
nums, return the largest subset in which every pair (a, b) satisfies a % b == 0 or b % a == 0. Return any such subset. Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 2 * 10^9.💡 Core Algorithmic Approaches
- Sort
nums; in a sorted divisible chain it suffices that each element divides the next larger one. - Let
dp[i]be the length of the longest divisible subset ending at indexi. - For each
i, scan everyj < iwithnums[i] % nums[j] == 0and takedp[j] + 1. - Keep a
parentarray and walk back from the index with the largestdpto reconstruct the subset.
💻 Benchmark Python3 Implementation
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
dp = [1] * n
parent = [-1] * n
best = 0
for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > dp[best]:
best = i
res = []
cur = best
while cur != -1:
res.append(nums[cur])
cur = parent[cur]
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the pair loop dominates; the sort is O(n log n).
💾 Space Complexity
O(n): the dp and parent arrays.
⚠️ Interview Pitfalls & Follow-ups
- Skipping the sort: without it, divisibility does not propagate along the chain and the DP order is invalid.
- Testing
nums[j] % nums[i] == 0: after sorting only the smaller value can divide the larger, so the check isnums[i] % nums[j]. - Returning
dpinstead of the subset: the answer is the reconstructed list of values. - Assuming the chain condition is transitive: divisibility must hold for the specific pair being chained, not merely across the whole set.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.