0/1 Knapsack

0_1_knapsack.py

class Solution:
    def knapsack(self, knapsack, target, i, n):
        if target < 0:
            return -1
        if i >= n:
            return 0
        key = (i, target)
        if key in self.cache:
            return self.cache[key]
        a = 1 + self.knapsack(knapsack, target - knapsack[i], i + 1, n)
        b = self.knapsack(knapsack, target, i + 1, n)
        res = max(a, b)
        self.cache[key] = res
        return res
    
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum & 1:
            return []
        knapsack = [el for el in range(2, finalSum + 1, 2)]
        n = len(knapsack)
        self.cache = {}
        self.knapsack(knapsack, finalSum, 0, n)
        return knapsack