Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Largest Divisible Subset

MEDIUMProblemSolveExternal Links

Description

You are given a set of distinct positive integers nums. Your task is to find the largest subset answer such that for every pair of elements (answer[i], answer[j]) in this subset, one of the following conditions holds:

  • answer[i] % answer[j] == 0 (the first element is divisible by the second), or
  • answer[j] % answer[i] == 0 (the second element is divisible by the first)

In other words, every pair in the subset must have a divisibility relationship — the larger number must be a multiple of the smaller number.

If there are multiple valid subsets of the same maximum size, return any one of them.

Examples

Example 1

Input: nums = [1, 2, 3]

Output: [1, 2]

Explanation: We need every pair in the subset to satisfy divisibility. Consider all subsets of size 2 or more:

  • {1, 2}: 2 % 1 == 0 ✓. Valid.
  • {1, 3}: 3 % 1 == 0 ✓. Valid.
  • {2, 3}: 3 % 2 == 1 ✗ and 2 % 3 == 2 ✗. Neither divides the other. Invalid.
  • {1, 2, 3}: The pair (2, 3) fails divisibility. Invalid.

The largest valid subsets have size 2. We return [1, 2] (though [1, 3] is also accepted).

Example 2

Input: nums = [1, 2, 4, 8]

Output: [1, 2, 4, 8]

Explanation: Every pair in the full array satisfies divisibility: 2 % 1 == 0, 4 % 2 == 0, 4 % 1 == 0, 8 % 4 == 0, 8 % 2 == 0, 8 % 1 == 0. Since the entire array forms a valid divisible subset, we return all four elements.

Example 3

Input: nums = [1, 2, 3, 4, 8]

Output: [1, 2, 4, 8]

Explanation: Although 3 divides into 1 (3 % 1 == 0), it does not have a divisibility relationship with 2, 4, or 8 (3 % 2 ≠ 0, 4 % 3 ≠ 0, 8 % 3 ≠ 0). So 3 cannot be part of the chain [1, 2, 4, 8]. The largest divisible subset is [1, 2, 4, 8] with length 4.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • 1 ≤ nums[i] ≤ 2 × 10⁹
  • All integers in nums are unique

Editorial

Brute Force

Intuition

The most straightforward approach is to generate every possible subset of the array and check which ones satisfy the divisibility condition. Among all valid subsets, we return the largest one.

Think of it like choosing guests for a very exclusive dinner party. The rule is: for any two guests seated together, one must be a "factor" of the other (in terms of the numbers they represent). You try every possible guest list — all singles, all pairs, all triples, and so on — and pick the largest group where everyone follows the rule.

For each candidate subset, we verify the divisibility property by checking every pair of elements. If the larger element is divisible by the smaller for all pairs, the subset is valid.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3]:

Step 1: Start with an empty subset. We explore all possible subsets using recursion.

  • current = [], best = []

Step 2: Try including nums[0] = 1. current = [1].

  • Length 1 > 0 → update best = [1].

Step 3: Try adding nums[1] = 2 to [1]. Check: does 2 have a divisibility relationship with every element in [1]? 2 % 1 == 0 ✓.

  • current = [1, 2]. Length 2 > 1 → best = [1, 2].

Step 4: Try adding nums[2] = 3 to [1, 2]. Check: 3 % 1 == 0 ✓, but 3 % 2 == 1 ✗ and 2 % 3 == 2 ✗.

  • 3 cannot be added alongside 2. Skip.

Step 5: Backtrack. Remove 2 from [1, 2]. Now current = [1]. Try adding nums[2] = 3.

  • Check: 3 % 1 == 0 ✓. current = [1, 3]. Length 2 == best length 2. No improvement.

Step 6: Backtrack. Remove 1. Try starting with nums[1] = 2.

  • current = [2]. Try adding 3: 3 % 2 ≠ 0 and 2 % 3 ≠ 0 ✗. Cannot add.
  • Try nums[2] = 3 alone: current = [3]. Length 1 < best.

Step 7: All subsets explored. Largest valid subset: [1, 2] with length 2.

Result: [1, 2]

Algorithm

  1. Initialize best as an empty list to track the largest valid subset
  2. Define recursive function solve(index, current):
    • If current is longer than best, update best
    • For each index i from index to n-1:
      • Check if nums[i] has a divisibility relationship with every element already in current
      • If yes: add nums[i] to current, recurse with i + 1, then remove it (backtrack)
  3. Call solve(0, []) and return best

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> best;

    void solve(vector<int>& nums, int n, int index, vector<int>& current) {
        if (current.size() > best.size()) {
            best = current;
        }
        for (int i = index; i < n; i++) {
            bool canAdd = true;
            for (int x : current) {
                if (nums[i] % x != 0 && x % nums[i] != 0) {
                    canAdd = false;
                    break;
                }
            }
            if (canAdd) {
                current.push_back(nums[i]);
                solve(nums, n, i + 1, current);
                current.pop_back();
            }
        }
    }

    vector<int> largestDivisibleSubset(vector<int>& nums) {
        best.clear();
        int n = nums.size();
        vector<int> current;
        solve(nums, n, 0, current);
        return best;
    }
};
class Solution:
    def largestDivisibleSubset(self, nums):
        n = len(nums)
        best = []

        def solve(index, current):
            nonlocal best
            if len(current) > len(best):
                best = current[:]
            for i in range(index, n):
                if all(nums[i] % x == 0 or x % nums[i] == 0 for x in current):
                    current.append(nums[i])
                    solve(i + 1, current)
                    current.pop()

        solve(0, [])
        return best
import java.util.*;

class Solution {
    private List<Integer> best = new ArrayList<>();

    public List<Integer> largestDivisibleSubset(int[] nums) {
        best.clear();
        solve(nums, nums.length, 0, new ArrayList<>());
        return best;
    }

    private void solve(int[] nums, int n, int index, List<Integer> current) {
        if (current.size() > best.size()) {
            best = new ArrayList<>(current);
        }
        for (int i = index; i < n; i++) {
            boolean canAdd = true;
            for (int x : current) {
                if (nums[i] % x != 0 && x % nums[i] != 0) {
                    canAdd = false;
                    break;
                }
            }
            if (canAdd) {
                current.add(nums[i]);
                solve(nums, n, i + 1, current);
                current.remove(current.size() - 1);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ × n²)

There are 2ⁿ possible subsets. For each subset, we verify the divisibility property by checking all pairs, which takes O(n²) in the worst case. Total: O(2ⁿ × n²).

Space Complexity: O(n)

The recursion depth is at most n, and the current subset holds at most n elements. So auxiliary space is O(n).

Why This Approach Is Not Efficient

With n up to 1,000, the brute force generates up to 2¹⁰⁰⁰ subsets — a number vastly larger than the number of atoms in the universe. This is completely infeasible.

The key insight that unlocks a better solution comes from sorting. If we sort the array first, a critical property emerges: for any valid divisible subset in sorted order, we only need to check if each element is divisible by the previous element in the chain (not all pairs). This is because divisibility is transitive: if a | b and b | c, then a | c. So once we sort and form a chain where each consecutive pair divides, all pairs in the subset automatically satisfy divisibility.

This transforms the problem into finding the longest chain in a sorted array where each element divides the next — structurally identical to the Longest Increasing Subsequence (LIS) problem, but using divisibility instead of strict inequality.

Bar chart comparing exponential brute force time versus quadratic DP time for n=1000
Bar chart comparing exponential brute force time versus quadratic DP time for n=1000

Optimal Approach - Sort and DP with Parent Backtracking

Intuition

After sorting the array, the problem transforms beautifully. In a sorted array, for any valid divisible subset, the elements form a chain where each element divides the next: a₁ | a₂ | a₃ | ... | aₖ. This is because in sorted order, the smaller numbers come first, and we only need to verify that the next (larger) number is divisible by the previous one.

Why does checking only consecutive pairs suffice? Because of the transitive property of divisibility. If 4 divides 8 and 2 divides 4, then 2 automatically divides 8. So once we build a chain where each consecutive pair satisfies divisibility, every non-consecutive pair also satisfies it.

This reduces the problem to finding the longest divisibility chain in a sorted array — which is structurally identical to the classic Longest Increasing Subsequence (LIS) problem. Instead of asking "is nums[i] > nums[j]?", we ask "is nums[i] % nums[j] == 0?"

We use a dp array where dp[i] stores the length of the longest divisible chain ending at sorted index i. A parent array records which previous element led to each dp[i] value, allowing us to reconstruct the actual subset by backtracking from the maximum.

Step-by-Step Explanation

Let's trace through with nums = [1, 2, 3, 4, 8] (already sorted):

Step 1: Initialize dp = [1, 1, 1, 1, 1] and parent = [0, 1, 2, 3, 4]. Each element starts as its own chain of length 1.

Step 2: Process i=1 (nums[1]=2). Check j=0: 2 % 1 == 0 ✓. dp[0]+1 = 2 > 1. Update dp[1] = 2, parent[1] = 0.

  • dp = [1, 2, 1, 1, 1]. Chain at 1: [1, 2].

Step 3: Process i=2 (nums[2]=3). Check j=0: 3 % 1 == 0 ✓. dp[0]+1 = 2 > 1. Update dp[2] = 2, parent[2] = 0.

  • dp = [1, 2, 2, 1, 1]. Chain at 2: [1, 3].

Step 4: Still i=2. Check j=1: 3 % 2 == 1 ≠ 0 ✗. 3 is not a multiple of 2. Cannot extend chain from index 1.

Step 5: Process i=3 (nums[3]=4). Check j=0: 4 % 1 == 0 ✓. dp[3] = 2, parent[3] = 0.

Step 6: Still i=3. Check j=1: 4 % 2 == 0 ✓. dp[1]+1 = 3 > 2. Update dp[3] = 3, parent[3] = 1.

  • dp = [1, 2, 2, 3, 1]. Chain at 3: [1, 2, 4].

Step 7: Still i=3. Check j=2: 4 % 3 == 1 ≠ 0 ✗. 4 is not a multiple of 3. Skip.

Step 8: Process i=4 (nums[4]=8). Check j=0: 8 % 1 == 0 ✓. dp[4] = 2.

Step 9: Still i=4. Check j=1: 8 % 2 == 0 ✓. dp[1]+1 = 3 > 2. dp[4] = 3, parent[4] = 1.

Step 10: Still i=4. Check j=2: 8 % 3 == 2 ≠ 0 ✗. 8 is not a multiple of 3. Skip.

Step 11: Still i=4. Check j=3: 8 % 4 == 0 ✓. dp[3]+1 = 4 > 3. Update dp[4] = 4, parent[4] = 3.

  • dp = [1, 2, 2, 3, 4]. Chain at 4: [1, 2, 4, 8].

Step 12: DP complete. Maximum dp = 4 at index 4. Backtrack: idx=4 (8) → parent=3 (4) → parent=1 (2) → parent=0 (1). Self-reference, stop.

Result: Reverse collected [8, 4, 2, 1] → [1, 2, 4, 8].

Sort + DP with Parent Array — Divisibility Chain Building — Watch how we fill dp and parent arrays on the sorted input. For each element, we check all previous elements for divisibility and extend the longest valid chain.

Algorithm

  1. Sort the array in ascending order
  2. Create two arrays of size n:
    • dp[i] = 1 for all i (length of longest divisible chain ending at index i)
    • parent[i] = i for all i (predecessor index, self = no predecessor)
  3. For each index i from 1 to n-1:
    • For each index j from 0 to i-1:
      • If nums[i] % nums[j] == 0 AND dp[j] + 1 > dp[i]:
        • Update dp[i] = dp[j] + 1
        • Update parent[i] = j
  4. Find max_idx = index with the maximum dp value
  5. Backtrack from max_idx using parent pointers:
    • Collect nums[idx], move to parent[idx]
    • Stop when parent[idx] == idx
  6. Reverse collected elements and return

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> dp(n, 1);
        vector<int> parent(n);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }

        vector<int> result;
        int idx = maxIdx;
        while (parent[idx] != idx) {
            result.push_back(nums[idx]);
            idx = parent[idx];
        }
        result.push_back(nums[idx]);
        reverse(result.begin(), result.end());
        return result;
    }
};
class Solution:
    def largestDivisibleSubset(self, nums):
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = list(range(n))

        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j

        max_idx = 0
        for i in range(1, n):
            if dp[i] > dp[max_idx]:
                max_idx = i

        result = []
        idx = max_idx
        while parent[idx] != idx:
            result.append(nums[idx])
            idx = parent[idx]
        result.append(nums[idx])
        return result[::-1]
import java.util.*;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxIdx]) maxIdx = i;
        }

        List<Integer> result = new ArrayList<>();
        int idx = maxIdx;
        while (parent[idx] != idx) {
            result.add(nums[idx]);
            idx = parent[idx];
        }
        result.add(nums[idx]);
        Collections.reverse(result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

Sorting takes O(n log n). The DP filling phase uses two nested loops: the outer runs n times, the inner runs up to i times for each i. Total iterations: n(n-1)/2 = O(n²). The backtracking phase follows at most n parent pointers: O(n). Overall: O(n log n) + O(n²) + O(n) = O(n²).

With n ≤ 1,000, the total operations are roughly 500,000 — extremely efficient.

Space Complexity: O(n)

We store two auxiliary arrays (dp and parent) each of size n, plus the output list of at most n elements. The sorting is in-place for most implementations. Total auxiliary space: O(n).