⚡Flashcard Drill➔
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

  1. Sort nums; in a sorted divisible chain it suffices that each element divides the next larger one.
  2. Let dp[i] be the length of the longest divisible subset ending at index i.
  3. For each i, scan every j < i with nums[i] % nums[j] == 0 and take dp[j] + 1.
  4. Keep a parent array and walk back from the index with the largest dp to 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 is nums[i] % nums[j].
  • Returning dp instead 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems