LeetCode 368: Largest Divisible Subset Solution in Python – A Step-by-Step Guide

What Is LeetCode 368: Largest Divisible Subset?

LeetCode 368: Largest Divisible Subset provides an array of distinct positive integers, and your task is to find the largest subset where for every pair (a, b), either a divides b or b divides a. The subset doesn’t need to be contiguous, and you return any valid largest subset. It’s a problem that tests your ability to optimize subset selection!

Problem Statement

• Input:
• nums: List of distinct positive integers.
• Output: List[int] - Largest subset where every pair is divisible.
• Rules:
• For any a, b in the subset, a % b == 0 or b % a == 0.
• Return any valid largest subset if multiple exist.

Constraints

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10⁹

Examples

• Input: nums = [1,2,3]
• Output: [1,2]
• [1,2]: 1 divides 2.
• [1,3]: 1 divides 3.
• [1,2] and [1,3] are largest (size 2), return [1,2].
• Input: nums = [1,2,4,8]
• Output: [1,2,4,8]
• All pairs divisible (1 divides 2, 2 divides 4, 4 divides 8).
• Input: nums = [4,8,16]
• Output: [4,8,16]
• 4 divides 8, 8 divides 16.

These show the divisible chain—let’s solve it!

Understanding the Problem: Finding the Largest Divisible Subset

To tackle LeetCode 368 in Python, we need to: 1. Identify a subset where every pair satisfies the divisibility condition. 2. Maximize the subset’s size. 3. Return any valid largest subset.

A naive approach might test all subsets, but that’s exponential. Instead, we’ll use:

• Best Solution: Dynamic programming with path tracking—O(n²) time, O(n) space—fast and efficient.
• Alternative Solution: Backtracking—O(2ⁿ) time, O(n) space—intuitive but slow.

Let’s optimize with the best solution!

Best Solution: Dynamic Programming with Path Tracking

Why This Is the Best Solution

The dynamic programming approach runs in O(n²) time by building the largest divisible subset incrementally, using sorted order and tracking predecessors. It’s the most efficient—leveraging the fact that divisibility chains can be constructed like a longest increasing subsequence (LIS) variant!

How It Works

Think of it like building a chain:

• Sort: Sort nums ascending (ensures divisibility checks go one way: smaller divides larger).
• DP:
• dp[i]: Size of largest divisible subset ending at nums[i].
• prev[i]: Index of previous element in the subset.
• Build: Iterate and check divisibility, update dp and prev.
• Reconstruct: Trace back from the max dp index.

It’s like linking numbers in a divisible sequence!

Step-by-Step Example

For nums = [1,2,4,8]:

• Sort: [1,2,4,8] (already sorted).
• DP Initialization:
• dp = [1,1,1,1] (each number alone is size 1).
• prev = [-1,-1,-1,-1] (no predecessors yet).
• Step 1: i=1 (2):
• Check 1: 2 % 1 = 0, dp[1] = dp[0] + 1 = 2, prev[1] = 0.
• dp = [1,2,1,1], prev = [-1,0,-1,-1].
• Step 2: i=2 (4):
• 4 % 1 = 0, dp[2] = 2, prev[2] = 0.
• 4 % 2 = 0, dp[2] = dp[1] + 1 = 3, prev[2] = 1.
• dp = [1,2,3,1].
• Step 3: i=3 (8):
• 8 % 1 = 0, dp[3] = 2, prev[3] = 0.
• 8 % 2 = 0, dp[3] = 3, prev[3] = 1.
• 8 % 4 = 0, dp[3] = dp[2] + 1 = 4, prev[3] = 2.
• dp = [1,2,3,4].
• Max Index: 3 (dp[3]=4).
• Reconstruct:
• 8 (i=3), prev[3]=2 → 4, prev[2]=1 → 2, prev[1]=0 → 1, prev[0]=-1 → stop.
• Result: [1,2,4,8].

For nums = [1,2,3]:

• DP: dp = [1,2,2], prev = [-1,0,0].
• Max Index: 1 or 2 (size 2).
• Result: [1,2] (or [1,3]).

Code with Explanation

Here’s the Python code using DP:

Copy codeclass Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        # Sort array to ensure divisibility checks go smaller to larger
        nums.sort()
        n = len(nums)

        # dp[i] = size of largest subset ending at nums[i]
        # prev[i] = index of previous element in subset
        dp = [1] * n
        prev = [-1] * n

        # Find largest subset ending at each index
        max_size = 1
        max_idx = 0
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
                    if dp[i] > max_size:
                        max_size = dp[i]
                        max_idx = i

        # Reconstruct the subset
        result = []
        while max_idx != -1:
            result.append(nums[max_idx])
            max_idx = prev[max_idx]

        return result

Explanation

• Lines 3-5: Handle empty input.
• Line 7: Sort nums for one-way divisibility checks.
• Lines 10-11: Initialize dp (size) and prev (path) arrays.
• Lines 14-22: DP loop:
• For each i, check all j < i.
• If nums[i] % nums[j] == 0 and adding j increases size, update dp[i] and prev[i].
• Track max size and index.
• Lines 24-28: Reconstruct by backtracking from max_idx.
• Time: O(n²)—nested loops.
• Space: O(n)—dp and prev arrays.

This is like building a divisibility chain—fast and smart!

Alternative Solution: Backtracking

Why an Alternative Approach?

The backtracking solution runs in O(2ⁿ) time by exploring all possible subsets to find the largest divisible one. It’s slower but shows the exhaustive process—great for understanding or small inputs!

How It Works

• Recurse: Try including/excluding each number, check divisibility.
• Track: Maintain current subset and max subset.
• Result: Return the largest valid subset.

Step-by-Step Example

For nums = [1,2,4]:

• Paths:
• [] → [1] → [1,2] → [1,2,4] (valid, size 3).
• [1] → [1,4] (valid, size 2).
• [2] → [2,4] (valid, size 2).
• [4] (size 1).
• Max: [1,2,4].

Code with Explanation

Copy codeclass Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums.sort()
        max_subset = []

        # Backtracking helper
        def backtrack(index, curr_subset):
            nonlocal max_subset
            if len(curr_subset) > len(max_subset):
                max_subset = curr_subset[:]

            for i in range(index, len(nums)):
                if all(nums[i] % x == 0 or x % nums[i] == 0 for x in curr_subset):
                    curr_subset.append(nums[i])
                    backtrack(i + 1, curr_subset)
                    curr_subset.pop()

        backtrack(0, [])
        return max_subset

Explanation

• Lines 7-17: backtrack:
• Update max_subset if current is larger.
• For each i, check divisibility with all in curr_subset.
• Include nums[i], recurse, exclude (backtrack).
• Time: O(2ⁿ)—exponential subset exploration.
• Space: O(n)—recursion stack and subset.

It’s like trying every divisibility combo!

Comparing the Two Solutions

• DP with Path Tracking (Best):
• Time: O(n²)—quadratic DP.
• Space: O(n)—arrays.
• Pros: Fast, scalable.
• Cons: Requires path tracking.
• Backtracking (Alternative):
• Time: O(2ⁿ)—exponential.
• Space: O(n)—stack.
• Pros: Intuitive exploration.
• Cons: Impractical for large n.

DP wins for efficiency!

Additional Examples and Edge Cases

• [1]: [1].
• [2,3]: [2] or [3].
• Large array: DP scales better.

Both work, DP is faster.

Complexity Breakdown

• DP:
• Time: O(n²).
• Space: O(n).
• Backtracking:
• Time: O(2ⁿ).
• Space: O(n).

DP excels for performance.

Key Takeaways

• DP: Chain divisors—fast and smart!
• Backtracking: Try all paths—clear but slow!
• Divisibility: Numbers align in order.
• Python Tip: DP rocks—see [Python Basics](/python/basics).

Final Thoughts: Find That Subset

LeetCode 368: Largest Divisible Subset in Python is a divisibility challenge. DP with path tracking is the efficiency champ, while backtracking builds intuition. Want more? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 416: Partition Equal Subset Sum. Ready to divide? Visit Solve LeetCode 368 on LeetCode and grab that subset today!