Find largest divisible subset in array

Find the largest divisible subset in a given array. A subset is divisible if for every pair (x, y) in the subset, either x divides y or y divides x.

Hint

Initialization:

• Sort the input list of numbers.
• Start with an empty "track" list.

Recursive Exploration, for each number in the sorted list:

• Include:

  • If the track is empty or the current number is divisible by the last number in the track, add the current number to the track.
  • Recursively explore the remaining numbers in the list with the updated track.
  • Remove the last number from the track (backtracking).

• Exclude:

  • Recursively explore the remaining numbers in the list without adding the current number to the track.

When the end of the list is reached, if the current track has more numbers than the previously found largest subset, update the largest subset.

• Python
• Javascript
•  Run

def divisible(ls, track, result):
  if not ls:
    if len(track) > len(result):
      result[:] = track[:]
    
    return

  if not track or ls[0] % track[-1] == 0:
    track.append(ls[0])
    divisible(ls[1:], track, result)
    track.pop()
  
  divisible(ls[1:], track, result)

ls = [1, 16, 7, 8, 4]
ls.sort()

output = []

divisible(ls, [], output)

print(output)

function divisible(list, track, result) {
  if (list.length < 1) {
    if (track.length > result.length) {
      result.splice(0, result.length, ...track);
    }
    return;
  }

  if (track.length === 0 || list[0] % track.at(-1) === 0) {
    track.push(list[0]);
    divisible(list.slice(1), track, result);
    track.pop();
  }

  divisible(list.slice(1), track, result);
}

const list = [1, 16, 7, 8, 4];
const output = [];

divisible(list.sort((a, b) => a - b), [], output);

console.log(output);