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