# LeetCode 368: Largest Divisible Subset

## Problem Restatement

We are given a set of distinct positive integers `nums`.

Return the largest subset `answer` such that for every pair of numbers in `answer`, one number divides the other.

For any pair:

```python
answer[i], answer[j]
```

at least one of these must be true:

```python
answer[i] % answer[j] == 0
```

or:

```python
answer[j] % answer[i] == 0
```

If there are multiple valid largest subsets, return any one of them. The official examples include `nums = [1,2,3]`, where `[1,2]` or `[1,3]` is accepted, and `nums = [1,2,4,8]`, where the full array is valid.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of distinct positive integers `nums` |
| Output | Largest divisible subset |
| Pair rule | For every pair, one number must divide the other |
| Valid answers | Any largest valid subset may be returned |

Example function shape:

```python
def largestDivisibleSubset(nums: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3]
```

Valid answers include:

```python
[1, 2]
```

and:

```python
[1, 3]
```

Both have length `2`.

We cannot take `[1, 2, 3]` because:

```python
3 % 2 != 0
```

and:

```python
2 % 3 != 0
```

So `2` and `3` cannot both be in the same divisible subset.

Example 2:

```python
nums = [1, 2, 4, 8]
```

The whole list is valid:

```python
[1, 2, 4, 8]
```

because each larger number is divisible by each smaller number.

## First Thought: Try All Subsets

A brute force solution would generate every subset of `nums`.

For each subset, check whether every pair satisfies the divisibility rule.

There are:

```python
2 ** n
```

subsets.

This becomes too slow quickly.

We need to use structure.

## Key Insight

Sort the numbers.

After sorting, if we build a chain:

```python
a1 <= a2 <= a3 <= ...
```

and every next number is divisible by the previous number:

```python
a2 % a1 == 0
a3 % a2 == 0
```

then every later number is divisible by every earlier number.

Why?

Divisibility is transitive.

If:

```python
a2 % a1 == 0
```

and:

```python
a3 % a2 == 0
```

then `a3` is also divisible by `a1`.

So after sorting, the problem becomes similar to Longest Increasing Subsequence, except the transition condition is divisibility.

We compute the longest divisible chain ending at each index.

## Algorithm

Sort `nums`.

Create two arrays:

| Array | Meaning |
|---|---|
| `dp[i]` | Length of the largest divisible subset ending at `nums[i]` |
| `parent[i]` | Previous index before `i` in that subset |

Initialize:

```python
dp[i] = 1
parent[i] = -1
```

because every number alone is a valid subset.

For each `i`, check every `j < i`.

If:

```python
nums[i] % nums[j] == 0
```

then `nums[i]` can extend the subset ending at `nums[j]`.

Update:

```python
dp[i] = dp[j] + 1
parent[i] = j
```

if this gives a longer subset.

After filling DP:

1. Find the index with the largest `dp[i]`.
2. Follow `parent` links backward.
3. Reverse the result.

## Correctness

After sorting, every candidate subset can be written in non-decreasing order.

For a valid divisible chain ending at `nums[i]`, the previous element must be some `nums[j]` where `j < i` and:

```python
nums[i] % nums[j] == 0
```

The DP checks all such previous indices.

If a subset ending at `nums[j]` is valid, then appending `nums[i]` keeps the subset valid because `nums[i]` is divisible by `nums[j]`, and by transitivity it is also divisible by every earlier element in that chain.

Therefore, `dp[i]` correctly stores the length of the largest valid subset ending at `nums[i]`.

The `parent` array records the previous index that produced the best value, so following parent links reconstructs an actual largest subset.

The algorithm chooses the maximum over all ending indices, so it returns a largest divisible subset.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | For each `i`, we scan all earlier `j` |
| Space | `O(n)` | `dp`, `parent`, and output reconstruction |

Sorting costs `O(n log n)`, which is dominated by the DP.

## Implementation

```python
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)

        dp = [1] * n
        parent = [-1] * n

        best_len = 1
        best_index = 0

        for i in range(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

            if dp[i] > best_len:
                best_len = dp[i]
                best_index = i

        answer = []

        while best_index != -1:
            answer.append(nums[best_index])
            best_index = parent[best_index]

        answer.reverse()
        return answer
```

## Code Explanation

We sort first:

```python
nums.sort()
```

This lets us only check whether a later, larger number is divisible by an earlier, smaller number.

Each number starts as a subset of length `1`:

```python
dp = [1] * n
```

The parent array starts with `-1`:

```python
parent = [-1] * n
```

A value of `-1` means this number starts the chain.

For each pair `j < i`, we test divisibility:

```python
if nums[i] % nums[j] == 0:
```

If extending from `j` creates a longer chain, update both arrays:

```python
dp[i] = dp[j] + 1
parent[i] = j
```

We also track the best ending index:

```python
if dp[i] > best_len:
    best_len = dp[i]
    best_index = i
```

Finally, reconstruct by following parent links:

```python
while best_index != -1:
    answer.append(nums[best_index])
    best_index = parent[best_index]
```

This builds the answer backward, so we reverse it:

```python
answer.reverse()
```

## Testing

```python
def is_valid_subset(nums, subset):
    nums_count = {x: nums.count(x) for x in nums}

    for x in subset:
        if x not in nums_count or nums_count[x] == 0:
            return False
        nums_count[x] -= 1

    for i in range(len(subset)):
        for j in range(i + 1, len(subset)):
            a = subset[i]
            b = subset[j]
            if a % b != 0 and b % a != 0:
                return False

    return True

def run_tests():
    s = Solution()

    ans = s.largestDivisibleSubset([1, 2, 3])
    assert len(ans) == 2
    assert is_valid_subset([1, 2, 3], ans)

    ans = s.largestDivisibleSubset([1, 2, 4, 8])
    assert ans == [1, 2, 4, 8]

    ans = s.largestDivisibleSubset([4, 8, 10, 240])
    assert len(ans) == 3
    assert is_valid_subset([4, 8, 10, 240], ans)

    ans = s.largestDivisibleSubset([3])
    assert ans == [3]

    ans = s.largestDivisibleSubset([2, 3, 4, 9, 8])
    assert len(ans) == 3
    assert is_valid_subset([2, 3, 4, 9, 8], ans)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]` | Multiple valid largest answers |
| `[1, 2, 4, 8]` | Entire array is valid |
| `[4, 8, 10, 240]` | Checks reconstruction |
| Single element | Minimum case |
| Mixed chains | Confirms DP chooses a valid longest chain |