Recurive Backtracking: Leet Code – Remove Boxes (Python)

I was working on this leetcode: https://leetcode.com/problems/remove-boxes/ and my answer is only slightly off for certain test cases. Any advice would be appreciated.

The problem is outlined as the following:

You are given several boxes with different colors represented by different positive numbers.

You may experience several rounds to remove boxes until there is no box left. Each time you can choose some continuous boxes with the same color (i.e., composed of k boxes, k >= >1), remove them and get k * k points.

Return the maximum points you can get.

Example 1:

Input: boxes = [1]
Output: 1 => (1*1)

Example 2:

Input: boxes = [1,1,1]
Output: 9 => (3*3)

Example 3:

Input: boxes = [1,3,2,2,2,3,4,3,1]
Output: 23
Explanation:
[1, 3, 2, 2, 2, 3, 4, 3, 1] 
----> [1, 3, 3, 4, 3, 1] (3*3=9 points) 
----> [1, 3, 3, 3, 1] (1*1=1 points) 
----> [1, 1] (3*3=9 points) 
----> [] (2*2=4 points)

I decided to use recursive backtracking to try and solve this, and my code is the following:

from copy import deepcopy as copy
class Solution: 
    # Main function
    def backtrack(self, boxes, score, seen={}):
        # Make list hashable
        hashable = tuple(boxes)
        
        if len(boxes) == 0:
            return score
        
        if hashable in seen:
            return seen[hashable]
        
        pos_scores = []
        
        loop_start = 0
        loop_end = len(boxes)
        
        while(loop_start < loop_end):
            # keep original boxes for original 
            box_copy = copy(boxes)
            
            # Returns the continous from starting point
            seq_start, seq_end = self.find_seq(box_copy, loop_start)
            
            # Return the box array without the seqence, and the score from removal
            new_boxes, new_score = self.remove_sequence(box_copy, seq_start, seq_end)
            
            # Backtrack based off the new box list and new score
            pos_scores.append(self.backtrack(box_copy, score+new_score, seen))
            
            # Next iteration will use a fresh copy of the boxes
            loop_start = seq_end
            
        seen[hashable] = max(pos_scores)
        return seen[hashable]
        
    def remove_sequence(self, boxes, start, end):
        rem_counter = 0

        for i in range(start, end):
            boxes.pop(i - rem_counter)
            rem_counter += 1

        dist = (end - start)
        score = dist * dist
        return boxes, score
    
    def find_seq(self, boxes, start):
        color = boxes[start]
        end = start

        for i in range(start, len(boxes)):
            if boxes[i] == color:
                end += 1
            else:
                break

        return start, end
    
    def removeBoxes(self, boxes) -> int:
        return self.backtrack(boxes, 0, {})

My issue is that my code has worked for smaller examples, but is slightly off for the larger ones. I believe my code is almost there, but I think I’m missing an edge case. Any tips would be greatly appreciated. For example, I get the correct answer for [1,1,2,1,2] as well as most test cases. However my answer for the third example is 21, not 23.

Answer

Per @Armali’s comment, the solution to the code above is to use

        hashable = tuple(boxes), score