Today we are going to share a recursive solution for subset sum problem. If you are a python beginner and want to start learning the python programming, then keep your close attention in this tutorial as I am going to share a recursive solution for subset sum problem.
To increase your Python knowledge, practice all Python programs, here is a collection of 100+ Python problems with solutions.
Copy the below python program and execute it with the help of python compiler.
def isSubsetSum(set,n, sum) :
# Base Cases
if (sum == 0) :
if (n == 0 and sum != 0) :
# If last element is greater than
# sum, then ignore it
if (set[n - 1] > sum) :
return isSubsetSum(set, n - 1, sum);
# else, check if sum can be obtained
# by any of the following
# (a) including the last element
# (b) excluding the last element
return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1])
# Driver program to test above function
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(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.