backtracking.sum_of_subsets

The sum-of-subsetsproblem 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.

Attributes

max_sum
nums
result

Functions

create_state_space_tree(→ None)	Creates a state space tree to iterate through each branch using DFS.
generate_sum_of_subsets_soln(→ list[list[int]])

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.

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

backtracking.sum_of_subsets.max_sum = 9

backtracking.sum_of_subsets.nums = [3, 34, 4, 12, 5, 2]

backtracking.sum_of_subsets.result = []