Python | Simple Solution With Detailed Explanation
Logic\nSince we have to find the largest subset for which every pair must satisfy either of the following-\n1. subset[i] % subset[j] == 0 OR\n2. subset[j] % sub
## Logic\nSince we have to find the largest subset for which every pair must satisfy either of the following-\n1. subset[i] % subset[j] == 0 OR\n2. subset[j] % subset[i] == 0\n\nSo if we sort our given array **nums** then we just need to find the laregest subset of **nums** for which every pair(i, j) must satisfy **subset[j] % subset[i] == 0** as subset[i] % subset[j] == 0 will always be false for sorted array.\n\nNow, once the given array is sorted, we will iterate it for every index and store the previous elements which satisfies the above modulo condition in divisibleSubset dp array.\nAt the end we will return the longest divisibleSubset.\n\nNow the question arises as how to efficiently fill the divisibleSubset dp array.\nTo solve the above question we will check for each index how many previous elements satisfy the above modulo equation and whether the divisibleSubset of current index is less than the divisibleSubset of previous indexes.\nIf any previous index satisfies the above condition then we will update the divisibleSubset of currentIndex by merging the the divisibleSubset of previous index with current item.\n\n```\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        divisibleSubset = [[num] for num in nums]\n        \n        for i in range(len(nums)):\n            for j in range(i):\n                if (nums[i] % nums[j]) == 0 and len(divisibleSubset[i]) < len(divisibleSubset[j]) + 1:\n                    divisibleSubset[i] = divisibleSubset[j] + [nums[i]]\n                    \n        return max(divisibleSubset, key=len)\n        \n```\n\n***If you liked the above solution then please upvote!***
['Dynamic Programming', 'Python']