Largest divisible subset

Array Math Dynamic Programming Sorting

49.4% acceptance

Jan 12, 2026

6840

328

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {
    let mut nums = nums;
    nums.sort_unstable();
    let n = nums.len();
    
    let mut dp = vec![1; n];
    let mut prev = vec![-1; n];
    let mut max_idx = 0;
    
    for i in 1..n {
      for j in 0..i {
        if nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i] {
          dp[i] = dp[j] + 1;
          prev[i] = j as i32;
        }
      }
      if dp[i] > dp[max_idx] {
        max_idx = i;
      }
    }
    
    let mut result = Vec::new();
    let mut idx = max_idx as i32;
    while idx != -1 {
      result.push(nums[idx as usize]);
      idx = prev[idx as usize];
    }
    
    result.reverse();
    result
  }
}