Python program for subset sum problem: In computer science, the subset sum problem is an important decision problem in complexity theory and cryptography. There are several equivalent formulations of the problem. One of them is: given a set of integers, is there a non-empty subset whose sum is zero.
Copy the below program python program and execute it to see the real time output.
def SubsetSum(set, n, sum) :
# Base Cases
if (sum == 0) :
if (n == 0 and sum != 0) :
# ignore if last element is > sum
if (set[n - 1] > sum) :
return SubsetSum(set, n - 1, sum);
# else,we check the sum
# (1) including the last element
# (2) excluding the last element
return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sumset[n-1])
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (SubsetSum(set, n, sum) == True) :
print("Found a subset with given sum")
print("No subset with given sum")
Found a subset with given sum
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.