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 sequences with the largest size, return any of them.
Example 1:
Input:
n = 3
arr = [1,2,3]
Output:
[1,2]
Explanation:
Largest Divisble Subset is [1,2].
Example 2:
Input:
n = 4
arr = [1,2,4,8]
Output:
[1,2,4,8]
Your Task:
You don't have to read input or print anything. Your task is to complete the function LargestSubset() which takes the integer n and array arr and returns the Largest Divisible Subset.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
Constraint:
1 <= n <= 1000
1 <= arr[i] <= 2 * 10^{9}

见题面

见题面