sum of subsets 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.
"""
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.
"""
def generate_sum_of_subsets_soln(nums, max_sum):
result = []
path = []
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, max_sum, num_index, path, result, remaining_nums_sum):
"""
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.
"""
if sum(path) > max_sum or (remaining_nums_sum + sum(path)) < max_sum:
return
if sum(path) == max_sum:
result.append(path)
return
for num_index in range(num_index, len(nums)):
create_state_space_tree(
nums,
max_sum,
num_index + 1,
path + [nums[num_index]],
result,
remaining_nums_sum - nums[num_index],
)
"""
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())
"""
nums = [3, 34, 4, 12, 5, 2]
max_sum = 9
result = generate_sum_of_subsets_soln(nums, max_sum)
print(*result)
