---
title: "LeetCode #904: Fruit Into Baskets"
url: https://perrotta.dev/2025/12/leetcode-%23904-fruit-into-baskets/
last_updated: 2026-01-03
---


[LeetCode #904: Fruit Into Baskets](https://leetcode.com/problems/fruit-into-baskets):

The problem statement is a bit confusing.

Once understood, it's a DP problem.

```python
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        from functools import cache

        n = len(fruits)

        @cache
        def solve(i, choices):
            if i < 0:
                return 0

            # take if possible
            a = None
            if len(choices) < 2 or fruits[i] in choices:
                a = 1 + solve(i - 1, tuple(set(choices + (fruits[i],))))

            # do not take
            # this is only a valid choice in the beginning
            b = None
            if len(choices) == 0:
                b = 0 + solve(i - 1, choices)

            return max(el for el in (a, b, 0) if el is not None)

        return solve(n - 1, tuple())
```

For memoization we need a tuple. We cannot use a list or a set.

This is a handy pattern to extract the `max` of a tuple/list when certain of its
elements can be `None`:

```python
max(el for el in (a, b, 0) if el is not None)
```