backtracking.sum_of_subsets

The sum-of-subsets problem states that a set of non-negative 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.

Functions

create_state_space_tree(→ None)	Creates a state space tree to iterate through each branch using DFS.
generate_sum_of_subsets_solutions(→ list[list[int]])	The main function. For list of numbers 'nums' find the subsets with sum

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)
[]