Largest Divisible Subset LeetCode solution in Rust

1
impl Solution {
2
  pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {
3
    if nums.len() <= 1 {
4
      return nums;
5
    }
6
    let mut nums: Vec<i32> = nums;
7
    nums.sort();
8
    let mut ans: Vec<(usize, i32)> = Vec::new();
9

10
    let mut max: i32 = 0;
11
    let mut idx_ans: usize = 0;
12

13
    for i in 0..nums.len() {
14
      ans.push((i, 1));
15
      for j in 0..i {
16
        if nums[i] % nums[j] == 0 && ans[i].1 <= ans[j].1 {
17
          ans[i].0 = j;
18
          ans[i].1 = ans[j].1 + 1;
19

20
          if max < ans[i].1 {
21
            max = ans[i].1;
22
            idx_ans = i;
23
          }
24
        }
25
      }
26
    }
27

28
    let mut result: Vec<i32> = Vec::new();
29
    let mut idx = idx_ans;
30

31
    while ans[idx].1 > 1 {
32
      result.push(nums[idx]);
33
      idx = ans[idx].0;
34
    }
35
    result.push(nums[idx]);
36

37
    result
38
  }
39
}