368. Largest Divisible Subset - Detailed Explanation

Problem Statement

Given a set of distinct positive integers nums, return the largest subset such that for every pair (Si, Sj) in the subset, either Si % Sj == 0 or Sj % Si == 0. If there are multiple solutions, return any.

Examples

Example 1

Input  nums = [1,2,3]
Output [1,2]  (or [1,3])

Example 2

Input  nums = [1,2,4,8]
Output [1,2,4,8]

Constraints

• 1 ≤ nums.length ≤ 1000
• 1 ≤ nums[i] ≤ 10⁹
• All values of nums are distinct

Intuition

If you sort nums, any valid divisible pair in the subset must respect the sorted order. You can build up the solution by considering each number as the largest in a subset ending there, and keeping track of the best chain you can attach to it.

Dynamic Programming Formulation

1. Sort nums in ascending order.
2. Let dp[i] = size of the largest divisible subset ending at index i.
3. Let prev[i] = index of the previous element in that subset (or -1 if none).
4. Initialize each dp[i] = 1, prev[i] = -1.
5. For each i from 0 to n−1:
   • For each j from 0 to i−1:
     • If nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
       • Update dp[i] = dp[j] + 1
       • Set prev[i] = j
6. Track the index maxIdx where dp is largest.
7. Reconstruct the subset by following prev from maxIdx back to -1.

Step‑by‑Step Walkthrough

nums = [1,2,4,7,8]

1. Sort (already sorted).
2. Initialize

   dp   = [1,1,1,1,1]
   prev = [-1,-1,-1,-1,-1]
   

3. i=1 (num=2):
   • j=0 (1): 2%1==0, dp[0]+1=2>1 → dp[1]=2, prev[1]=0
4. i=2 (num=4):
   • j=0: 4%1==0 → dp[2]=2, prev[2]=0
   • j=1: 4%2==0 and dp[1]+1=3>2 → dp[2]=3, prev[2]=1
5. i=3 (num=7):
   • only j where divisible is none → dp[3]=1
6. i=4 (num=8):
   • j=0: 8%1==0 → dp[4]=2, prev[4]=0
   • j=1: 8%2==0 → dp[4]=3, prev[4]=1
   • j=2: 8%4==0 → dp[4]=4, prev[4]=2
   • j=3: skip
7. dp = [1,2,3,1,4], maxIdx = 4
8. Reconstruct: 8 ← prev[4]=2 → 4 ← prev[2]=1 → 2 ← prev[1]=0 → 1
   → subset = [1,2,4,8]

Complexity Analysis

• Time: O(n²) due to the double loop over i and j
• Space: O(n) for dp, prev, and the output list

Common Mistakes

• Forgetting to sort before DP
• Not initializing prev to -1 and handling reconstruction correctly
• Off‑by‑one when building the output in reverse order

Edge Cases

• Single element → return [that element]
• All primes (no divisible pairs) → return any single element
• Already fully divisible chain → returns the entire sorted list

Code Solutions

Python