Let's discuss how to find the largest divisible subset from a given set of distinct positive integers.

Naive Approach (Brute Force)

A straightforward, but inefficient, approach is to generate all possible subsets and check if each subset satisfies the divisibility condition. We keep track of the largest subset found so far that meets the criteria.

1. Generate all possible subsets of the given array.
2. For each subset, check if every pair of elements (answer[i], answer[j]) satisfies either answer[i] % answer[j] == 0 or answer[j] % answer[i] == 0.
3. Maintain the largest subset found so far.

Code (Python):

def get_all_subsets(nums):
    subsets = [[]]
    for num in nums:
        new_subsets = [subset + [num] for subset in subsets]
        subsets.extend(new_subsets)
    return subsets

def check_divisibility(subset):
    if not subset:
        return True
    for i in range(len(subset)):
        for j in range(i + 1, len(subset)):
            if subset[i] % subset[j] != 0 and subset[j] % subset[i] != 0:
                return False
    return True

def largest_divisible_subset_brute_force(nums):
    all_subsets = get_all_subsets(nums)
    largest_subset = []
    for subset in all_subsets:
        if check_divisibility(subset):
            if len(subset) > len(largest_subset):
                largest_subset = subset
    return largest_subset

Time Complexity: O(2ⁿ * n²), where n is the number of elements in nums. Generating all subsets takes O(2ⁿ) time, and checking each subset for divisibility takes O(n²) time.

Space Complexity: O(2ⁿ * n) in the worst case to store all subsets.

Optimal Approach (Dynamic Programming)

To solve this problem efficiently, we can use dynamic programming.

1. Sort the input array nums in ascending order. Sorting allows us to only check divisibility in one direction (smaller to larger).
2. Create two arrays:
   • dp[i] stores the size of the largest divisible subset ending at nums[i].
   • pre[i] stores the index of the previous element in the largest divisible subset ending at nums[i].
3. Initialize: Each dp[i] is initialized to 1, and each pre[i] is initialized to i.
4. Iterate through the sorted array: For each nums[i], iterate through all preceding elements nums[j] (where j < i). If nums[i] is divisible by nums[j], it means we can extend the divisible subset ending at nums[j] by adding nums[i].
   • If dp[j] + 1 > dp[i], update dp[i] to dp[j] + 1 and pre[i] to j.
5. Find the index with the maximum dp value: This index represents the end of the largest divisible subset.
6. Backtrack to construct the subset: Starting from the index with the maximum dp value, backtrack using the pre array to reconstruct the largest divisible subset.

Code (Python):

def largest_divisible_subset(nums):
    n = len(nums)
    nums.sort()
    dp = [1] * n
    pre = list(range(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[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    pre[i] = j
        if dp[i] > max_len:
            max_len = dp[i]
            max_index = i

    result = []
    curr = max_index
    while curr != pre[curr]:
        result.append(nums[curr])
        curr = pre[curr]
    result.append(nums[curr])

    return result

Time Complexity: O(n²), where n is the number of elements in nums. The nested loops dominate the runtime.

Space Complexity: O(n) to store the dp and pre arrays, as well as the result.

Edge Cases

• Empty input array: Return an empty list.
• Single element array: Return the array itself.
• Multiple possible solutions: The algorithm returns one of the possible largest divisible subsets.

By using dynamic programming, we significantly improve the efficiency compared to the brute-force approach.