Code to pick buckets for a list of value

Question

In my current project, I came across a scenario where there will be two sorted list of Decimal values. Let's call them bucket_list and value_list

1. Where bucket_list represents the sum of one or more elements from the value_list
2. value_list may have duplicate values
3. Every element in value_list should be picked only once (duplicate values are considered different elements)
4. In the end, all elements in bucket_list will have one or more element from value_list and no elements in value_list will be left without a mapping to bucket_list

After a lot of searches, I wrote the code with backtracking and greedy(I think). Below is the part of code that handles the part of the problem.

    class FindBucketMap(object):
        @classmethod
        def create_map_list(cls, bucket_list: list, value_list: list, bucket_map_list: list, i: int = 0):
            """
        Backtracking code to find possible bucket and value pair
        :param bucket_list: List of bucket values
        :param value_list: List of values to map to bucket
        :param bucket_map_list: List will be updated with the mapping of values from bucket_list to value_list
        :param i:
        :return:
        """
            if i >= len(bucket_list) or len(value_list) == 0:
                if i >= len(bucket_list) and len(value_list) == 0:
                    return True
                else:
                    return False
            bucket_map_prospect_list = []
            bucket_value = bucket_list[i]
            cls.create_map(bucket_value, value_list, [], bucket_map_prospect_list)
            if len(bucket_map_prospect_list) == 0:
                return False
            for bucket_map_prospect in bucket_map_prospect_list:
                temp_list = list(value_list)
                for x in bucket_map_prospect:
                    temp_list.remove(x)
                if cls.create_map_list(bucket_list, temp_list, bucket_map_list, i + 1):
                    bucket_map_list.append({"bucket": bucket_value, "split": bucket_map_prospect})
                    return True

        @classmethod
        def create_map(cls, value: Decimal, value_list: list, cur_list: list, map_list: list, i: int = 0):
            """
        Greedy code to find list of values that matches a sum
        :param value:  Expected Sum
        :param value_list: Possible values
        :param cur_list: Processed values
        :param map_list: List contains the possible combinations
        :param i:
        :return:
        """
            if value == Decimal(0):
                map_list.append(cur_list)
                return
            if value < Decimal(0):
                return
            while i < len(value_list):
                if value < value_list[i]:
                    return
                cls.create_map(value - value_list[i], value_list, cur_list + [value_list[i]], map_list, i + 1)
                i += 1

Please give reviews on the approach and the code.

EDIT 1:

For a large test case ( len(bucket_list) > 50 and len(value_list) > 1000 ), the program almost never ends. So I changed the code to the following:

    class FindBucketMap(object):
        @classmethod
        def create_map_list(cls, bucket_list: list, value_list: list, i: int = 0):
            if i >= len(bucket_list):
                return True
            return cls.create_map(bucket_list[i], bucket_list, value_list, [], i)

        @classmethod
        def create_map(cls, value: int, bucket_list: list, value_list: list, cur_list: list, i: int, j: int = 0):
            if value == 0:
                temp_list = list(value_list)
                for x in cur_list:
                   temp_list.remove(x)
                print(i, bucket_list[i], cur_list)
                result = cls.create_map_list(bucket_list, temp_list, i + 1)
                if result is True:
                    return [{"value": bucket_list[i], "split": cur_list}]
                elif isinstance(result, list):
                    return result + [{"value": bucket_list[i], "split": cur_list}]
                else:
                    return False
            if len(value_list) == 0 or value < Decimal(0):
                return False
            while j < len(value_list):
                if value < value_list[j]:
                    return False
                result = cls.create_map(value - value_list[j], bucket_list, value_list, cur_list + [value_list[j]], i,
                                        j + 1)
                if isinstance(result, list):
                    return result
                j += 1
            return False

This is faster than the first but still not fast enough.

Answer 1

Just a couple ways to shorten your code

This code

if i >= len(bucket_list) or len(value_list) == 0:
    if i >= len(bucket_list) and len(value_list) == 0:
        return True
    else:
        return False

can be written like this:

if i >= len(bucket_list) or not value_list:
    return i >= len(bucket_list) and not value_list

This allows you to return the boolean value this expression would evaluate too, and not value_list means the length of value_list is 0, or empty. I changed other occurances of this in your code as well.

---

This code

for x in bucket_map_prospect:
    temp_list.remove(x)

can be written like this:

temp_list.remove(x for x in bucket_map_prospect)

---

If you're going to use type hints, you might as well hint at what the method is returning. From this

def function(...):

to this

def function(...) -> bool/int/etc:

You'll see what I mean when you look at the updated code.

---

Updated Code

class FindBucketMap(object):
    """
    Class Docstring
    """
    @classmethod
    def create_map_list(cls, bucket_list: list, value_list: list, bucket_map_list: list, i: int = 0) -> bool:
        """
    Backtracking code to find possible bucket and value pair
    :param bucket_list: List of bucket values
    :param value_list: List of values to map to bucket
    :param bucket_map_list: List will be updated with the mapping of values from bucket_list to value_list
    :param i:
    :return:
    """
        if i >= len(bucket_list) or not value_list:
            return i >= len(bucket_list) and not value_list

        bucket_map_prospect_list = []
        bucket_value = bucket_list[i]
        cls.create_map(bucket_value, value_list, [], bucket_map_prospect_list)

        if not bucket_map_prospect_list:
            return False

        for bucket_map_prospect in bucket_map_prospect_list:
            temp_list = list(value_list)
            temp_list.remove(x for x in bucket_map_prospect)
            if cls.create_map_list(bucket_list, temp_list, bucket_map_list, i + 1):
                bucket_map_list.append({"bucket": bucket_value, "split": bucket_map_prospect})
                return True

    @classmethod
    def create_map(cls, value: Decimal, value_list: list, cur_list: list, map_list: list, i: int = 0) -> None:
        """
    Greedy code to find list of values that matches a sum
    :param value:  Expected Sum
    :param value_list: Possible values
    :param cur_list: Processed values
    :param map_list: List contains the possible combinations
    :param i:
    :return:
    """
        if value == Decimal(0):
            map_list.append(cur_list)
            return
        if value < Decimal(0):
            return
        while i < len(value_list):
            if value < value_list[i]:
                return
            cls.create_map(value - value_list[i], value_list, cur_list + [value_list[i]], map_list, i + 1)
            i += 1