Largest Divisible Subset

Problem Description

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Key Insights

• The problem requires finding subsets where elements are mutually divisible.
• Sorting the array helps to easily check divisibility relationships.
• Dynamic programming can be used to build up the largest divisible subset incrementally.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

To solve this problem, we can use a dynamic programming approach. We will:

1. Sort the input array nums. This allows us to only check for divisibility in one direction (smaller to larger).
2. Use a dynamic programming array dp where dp[i] represents the size of the largest divisible subset that ends with nums[i].
3. Maintain an array prev to track the previous index of the element that is part of the largest divisible subset for reconstruction purposes.
4. Iterate through each number, checking all previous numbers to see if they can form a valid divisible pair. Update the dp and prev arrays accordingly.
5. Finally, reconstruct the largest subset based on the indices stored in prev.

Code Solutions