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.

Examples

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]

Different Approaches

1️⃣ Tabulation

Code:

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        // Step 1: Sort the input array
        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<int> t(n, 1);       // t[i] = length of largest subset ending at nums[i]
        vector<int> parent(n);     // parent[i] = previous index in subset
        int maxi = 1;
        int longestIdx = 0;

        // Step 2: Initialize the parent array
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        // Step 3: DP loop to find largest divisible subset
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && (t[j] + 1) > t[i]) {
                    t[i] = t[j] + 1;
                    parent[i] = j;
                }
            }
            // ✅ Move this outside the inner loop
            if (t[i] > maxi) {
                longestIdx = i;
                maxi = t[i];
            }
        }

        // Step 4: Reconstruct the subset
        vector<int> ans;
        while (longestIdx != parent[longestIdx]) {
            ans.push_back(nums[longestIdx]);
            longestIdx = parent[longestIdx];
        }
        ans.push_back(nums[longestIdx]);

        // Step 5: Reverse the result
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
  • Due to nested loops
• Space Complexity:O(n)
  • For t[], and parent[]