sum of subset Algorithm

The Sum of Subsets Algorithm is a well-known combinatorial optimization technique that aims to find all possible subsets of a given set of numbers that add up to a specified target sum. This problem, also known as the subset sum problem, is a classical NP-hard problem in computer science and mathematics, with applications in cryptography, coding theory, and resource allocation, among other areas. The algorithm is based on the concept of backtracking, a systematic trial and error approach that explores the solution space by building a solution incrementally and removing a part of the solution when it violates constraints or does not lead to a valid solution. The Sum of Subsets Algorithm starts with an empty solution set and iteratively adds elements from the input set to the solution set, while keeping track of the current sum. If the current sum equals the target sum, the current subset is a valid solution and can be added to the list of solutions. If the current sum exceeds the target sum or if there are no more elements left to add, the algorithm backtracks by removing the last added element from the solution set and trying the next available element from the input set. This process is repeated until all possible combinations of elements have been explored. The algorithm can be further optimized by applying heuristics, such as sorting the input set in descending order or using dynamic programming techniques to avoid redundant computations.
def isSumSubset(arr, arrLen, requiredSum):
    """
    >>> isSumSubset([2, 4, 6, 8], 4, 5)
    False
    >>> isSumSubset([2, 4, 6, 8], 4, 14)
    True
    """
    # a subset value says 1 if that subset sum can be formed else 0
    # initially no subsets can be formed hence False/0
    subset = [[False for i in range(requiredSum + 1)] for i in range(arrLen + 1)]

    # for each arr value, a sum of zero(0) can be formed by not taking any element hence True/1
    for i in range(arrLen + 1):
        subset[i][0] = True

    # sum is not zero and set is empty then false
    for i in range(1, requiredSum + 1):
        subset[0][i] = False

    for i in range(1, arrLen + 1):
        for j in range(1, requiredSum + 1):
            if arr[i - 1] > j:
                subset[i][j] = subset[i - 1][j]
            if arr[i - 1] <= j:
                subset[i][j] = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

    # uncomment to print the subset
    # for i in range(arrLen+1):
    #     print(subset[i])
    print(subset[arrLen][requiredSum])


if __name__ == "__main__":
    import doctest

    doctest.testmod()

LANGUAGE:

DARK MODE: