# Solving Leetcode Interviews in Seconds with AI: Largest Divisible Subset


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "368" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> 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.   Example 1:  Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted.  Example 2:  Input: nums = [1,2,4,8] Output: [1,2,4,8]    Constraints:  1 <= nums.length <= 1000 1 <= nums[i] <= 2 * 109 All the integers in nums are unique.  

	# Explanation
	Here's a solution to find the largest divisible subset, along with an explanation:

*   **Sort the Input:** Sorting `nums` allows us to iterate in ascending order and efficiently check divisibility. This is crucial for building the dynamic programming table.
*   **Dynamic Programming:** We use a DP table `dp` where `dp[i]` stores the length of the largest divisible subset ending at `nums[i]`. We also maintain a `predecessor` array to reconstruct the actual subset.
*   **Reconstruction:** After filling the DP table, we find the index with the maximum `dp` value. We then backtrack using the `predecessor` array to build the largest divisible subset.

*   **Time & Space Complexity:** O(n^2) time, O(n) space

	
	# Code
	```python
	def largestDivisibleSubset(nums):
    n = len(nums)
    nums.sort()
    dp = [1] * n
    predecessor = [-1] * n
    max_len = 1
    max_index = 0

    for i in range(1, n):
        for j in range(i):
            if nums[i] % nums[j] == 0:
                if dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    predecessor[i] = j
        if dp[i] > max_len:
            max_len = dp[i]
            max_index = i

    result = []
    current = max_index
    while current != -1:
        result.append(nums[current])
        current = predecessor[current]

    return result
	```