Functions¶

Module Contents¶

backtracking.sum_of_subsets.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¶

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.

>>> path = []
>>> result = []
>>> create_state_space_tree(
...     nums=[1],
...     max_sum=1,
...     num_index=0,
...     path=path,
...     result=result,
...     remaining_nums_sum=1)
>>> path
[]
>>> result
[[1]]

backtracking.sum_of_subsets.generate_sum_of_subsets_solutions(nums: list[int], max_sum: int) → list[list[int]]¶

The main function. For list of numbers ‘nums’ find the subsets with sum equal to ‘max_sum’

>>> generate_sum_of_subsets_solutions(nums=[3, 34, 4, 12, 5, 2], max_sum=9)
[[3, 4, 2], [4, 5]]
>>> generate_sum_of_subsets_solutions(nums=[3, 34, 4, 12, 5, 2], max_sum=3)
[[3]]
>>> generate_sum_of_subsets_solutions(nums=[3, 34, 4, 12, 5, 2], max_sum=1)
[]