[Python] Short, simple, Time-95%, Space-87%, Iterative
Please feel free to ask questions and give suggestions to improve. Upvote if you liked the solution.\nMain Idea: \n If we traverse nums in ascending order and w
Please feel free to ask questions and give suggestions to improve. **Upvote** if you liked the solution.\n**Main Idea**: \n* If we traverse nums in ascending order and we need any 1 longest subset, we need to add exactly 1 new subset for each number. \n\t* If it\'s an extension of a subset we saw before, only 1 of the longest extensions need to be added. (Only the last value added in a subset matters (Anything divisible by the largest value will be divisible by the previously added smaller values (which are all factors of the largest value))\n\t* If it\'s not an extension, we build a new subset with just that value\n```\ndef largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n\t# We\'ll traverse values in nums in ascending order\n\tnums.sort()\n\t# Ordered (by length) list of valid subsets that are largest subset candidates\n\tsubsets = []\n\t\n\t# Add max-length subset for each value\n\tfor i, num in enumerate(nums):\n\t\t# Find the biggest subset we can add num to, and add this new subset to subsets (maintaining order)\n\t\tfor j in range(i-1, -1, -1):\n\t\t\t# If satisfies divisibility, insert into subsets (as per size, 1 bigger than previous subset)\n\t\t\tif not num%subsets[j][-1]:\n\t\t\t\t# Location of where to insert new extended subset (Alt.: Could binary search for it)\n\t\t\t\tk = next(filter(lambda k: len(subsets[j])!=len(subsets[k]), range(j+1, i)), i)\n\t\t\t\tsubsets.insert(k, subsets[j]+[num])\n\t\t\t\tbreak\n\t\telse:\n\t\t\t# num can\'t be added as an extension to any subset, create a blank one for it\n\t\t\tsubsets.insert(0, [num])\n\n\treturn subsets[-1]\n```
['Iterator', 'Python', 'Python3']