the sumofsubsetsproblem states that a set of nonnegative integers and a value m determine all possible subsets of the given set whose summation sum equal to given m summation of the chosen numbers must be equal to given number m and one number can be used only once creates a state space tree to iterate through each branch using dfs it terminates the branching of a node when any of the two conditions given below satisfy this algorithm follows depthfistsearch and backtracks when the node is not branchable remove the comment to take an input from the user printenter the elements nums listmapint input split printenter maxsum sum maxsum intinput creates a state space tree to iterate through each branch using dfs it terminates the branching of a node when any of the two conditions given below satisfy this algorithm follows depth fist search and backtracks when the node is not branchable remove the comment to take an input from the user print enter the elements nums list map int input split print enter max_sum sum max_sum int input
from __future__ import annotations


def generate_sum_of_subsets_soln(nums: list[int], max_sum: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []
    num_index = 0
    remaining_nums_sum = sum(nums)
    create_state_space_tree(nums, max_sum, num_index, path, result, remaining_nums_sum)
    return result


def create_state_space_tree(
    nums: list[int],
    max_sum: int,
    num_index: int,
    path: list[int],
    result: list[list[int]],
    remaining_nums_sum: int,
) -> None:
    
    if sum(path) > max_sum or (remaining_nums_sum + sum(path)) < max_sum:
        return
    if sum(path) == max_sum:
        result.append(path)
        return
    for index in range(num_index, len(nums)):
        create_state_space_tree(
            nums,
            max_sum,
            index + 1,
            [*path, nums[index]],
            result,
            remaining_nums_sum - nums[index],
        )



nums = [3, 34, 4, 12, 5, 2]
max_sum = 9
result = generate_sum_of_subsets_soln(nums, max_sum)
print(*result)