📘 Problem Statement
Given a set of distinct positive integers, return the largest subset such that for every pair of integers x and y in the subset, x % y == 0 or y % x == 0 (i.e., x is divisible by y or vice versa).
🧠 Key Insight
- The problem can be viewed as a variation of the Longest Increasing Subsequence (LIS) problem, but with the added constraint that each number in the subset must be divisible by another number.
- We can approach this problem using dynamic programming (DP), where the state of each number
nums[i] represents the longest divisible subset that ends with nums[i].
💡 Approach
- Sort the Input Array: Sorting the array ensures that we only need to check divisibility in one direction (
nums[i] % nums[j] == 0 for i > j).
- Dynamic Programming Array: For each element, find the largest divisible subset ending with that element.
- Track Parent Indices: To reconstruct the actual subset, we maintain a
parent array that keeps track of the previous element in the subset.
🐍 Python Code
python
class Solution:
def largestDivisibleSubset(self, nums):
if not nums:
return []
nums.sort() # Sort the numbers
n = len(nums)
dp = [1] * n # dp[i] stores the size of the largest divisible subset ending with nums[i]
parent = [-1] * n # To reconstruct the subset
max_size = 1
max_index = 0
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > max_size:
max_size = dp[i]
max_index = i
# Reconstruct the largest divisible subset
result = []
while max_index != -1:
result.append(nums[max_index])
max_index = parent[max_index]
return result[::-1] # Reverse the result as we collected it backwards
🔍 Step-by-Step Explanation
1. Sort the Input Array
python
nums.sort()
- Sorting the array ensures that once we find a valid divisible pair, we don't need to check for
nums[j] % nums[i], as nums[i] will always be greater than nums[j] when i > j.
2. Initialize DP Arrays
python
dp = [1] * n
parent = [-1] * n
dp[i] stores the size of the largest divisible subset that ends with nums[i].parent[i] helps to reconstruct the subset by keeping track of the previous element in the subset.
3. Populate the DP Array
python
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
parent[i] = j
- For each element
nums[i], check all previous elements nums[j] where j < i. If nums[i] % nums[j] == 0, update dp[i] to be the largest possible subset size ending at i.
4. Track the Largest Subset
python
if dp[i] > max_size:
max_size = dp[i]
max_index = i
- Keep track of the largest subset by checking the maximum value of
dp.
5. Reconstruct the Subset
python
result = []
while max_index != -1:
result.append(nums[max_index])
max_index = parent[max_index]
- Starting from the index of the largest subset, use the
parent array to trace back the elements of the subset.
💡 Example
python
Input: nums = [1, 2, 3, 8, 4, 6]
Output: [1, 2, 4, 8]
Explanation: The largest divisible subset is [1, 2, 4, 8] because:
- 1 % 2 == 0, 2 % 4 == 0, 4 % 8 == 0.
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(n²)Space ComplexityO(n)
- The time complexity is O(n²) due to the nested loops for checking divisibility between pairs of elements.
- The space complexity is O(n), as we only use two arrays
dp and parent.
🧵 Final Thoughts
This problem is a great example of how dynamic programming can optimize solutions to subset problems, and how sorting and number theory (specifically divisibility) can be combined for efficient solutions. It’s also an excellent problem for practicing subset reconstruction techniques.
- Dynamic programming is used to build solutions iteratively.
- The sorted array ensures we only check divisibility in one direction, making the process more efficient.