Largest Divisible Subset LeetCode solution in JavaScript

1
/** https://leetcode.com/problems/largest-divisible-subset/
2
 * @param {number[]} nums
3
 * @return {number[]}
4
 */
5
var largestDivisibleSubset = function (nums) {
6
  // Memo
7
  this.memo = new Map();
8

9
  // Sort the array so we can do dynamic programming from last number
10
  // We want to start from last number because it will be the largest number, the largest number will yield the largest subset because it can be divided many times
11
  nums.sort((a, b) => a - b);
12

13
  let out = [];
14

15
  // Perform dynamic programming on every numbers start from the last number
16
  for (let i = nums.length - 1; i >= 0; i--) {
17
    let curr = dp(nums, i);
18

19
    // Update the subset output if the current subset is larger
20
    if (curr.length > out.length) {
21
      out = curr;
22
    }
23
  }
24

25
  return out;
26
};
27

28
var dp = function (nums, currIdx) {
29
  // Return from memo
30
  if (this.memo.has(currIdx) === true) {
31
    return this.memo.get(currIdx);
32
  }
33

34
  let currSubset = [];
35

36
  // Look up all numbers before `currIdx`
37
  for (let i = currIdx - 1; i >= 0; i--) {
38
    // Check if the number at `currIdx` can be divided by number at `i`
39
    if (nums[currIdx] % nums[i] === 0) {
40
      // If they can be divided, perform dynamic programming on `i` to get the subset at `i`
41
      let prevSubset = dp(nums, i);
42

43
      // If the subset at `i` is longer than current subset, update current subset
44
      if (prevSubset.length > currSubset.length) {
45
        currSubset = prevSubset;
46
      }
47
    }
48
  }
49

50
  // Create the output which include number at `currIdx`
51
  let out = [...currSubset, nums[currIdx]];
52

53
  // Set memo
54
  this.memo.set(currIdx, out);
55

56
  return out;
57
};