How is it possible to memoize longest divisible subset using only the length (and end position)?

Question

The goal is to find the largest divisible subset. A divisible subset is a subset s.t. for every pair of elements i, j, either i is divisible by j or j is divisible by i. The general approach to solve this is to sort the numbers and realize that if a is divisible by b and b by c, that a must also be divisible by c. Here's the unmemoized recursion:

def largestDivisibleSubset0(self, nums: List[int]) -> List[int]:
    def backtrack(candidate, end):
        if len(candidate) > len(self.best):
            self.best = candidate[:]

        if end == n - 1:
            return

        for new_end in range(end+1, n):
            if not candidate or candidate[-1] % nums[new_end] == 0:
                backtrack(candidate+[nums[new_end]], new_end)

    nums.sort(reverse=True)
    n = len(nums)
    self.best = []
    backtrack([], -1)
    return self.best

Next, I tried to memoize. Forgive the poor style where self.best and memo are both tracked. I know it's redundant and that I'm not actually caching the local best but instead the global (side question: what is the best way to memoize this?)

def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
    def backtrack(candidate, end):
        if (len(candidate), end) in memo:
            return memo[(len(candidate), end)]

        if len(candidate) > len(self.best):
            self.best = candidate[:]

        if end == n - 1:
            return

        for new_end in range(end+1, n):
            if not candidate or candidate[-1] % nums[new_end] == 0:
                backtrack(candidate+[nums[new_end]], new_end)

        memo[(len(candidate), end)] = self.best

    nums.sort(reverse=True)
    n = len(nums)
    self.best = []
    memo = {}
    backtrack([], -1)
    return self.best

Here's what I don't understand. How is it an accurate representation of the state to simply consider the length of the current candidate, and not the last element? What if a subsequence ending in 5 has length x, equal to a subsequence ending in 4 — isn't it possible the latter one gets pruned from the search space, even if it might result in a longer divisible subset down the line?

Answer 1

end tells you the candidate subsequence ending.

What if a subsequence ending in 5 has length x, equal to a subsequence ending in 4

Then their end differs and thus their memo key differs and thus they don't prune each other.