Question
-
Topic
-
Subset Sum Problem in Java
I am trying to solve the Subset Sum Problem in Java. I have found a solution on a blog, but I am not sure I understand it correctly. Can someone help me understand the code and how it works?
The code is shown below:def subset_sum(set, n, sum):
if sum == 0:
return True
if n == 0:
return False
if set[n – 1] > sum:
return subset_sum(set, n – 1, sum)
return subset_sum(set, n – 1, sum) or subset_sum(set, n – 1, sum – set[n – 1])def main():
set = [1, 2, 3, 4, 5]
n = len(set)
sum = 10
print(subset_sum(set, n, sum))if __name__ == “__main__”:
main()
Can someone explain the following in the code:What does the subset_sum() function do?
How does the recursive call work?
What is the time and space complexity of the algorithm?
I would appreciate any help you can provide. Thank you!I have also attached the output of the code, which is True. This means that there is a subset of the given array that sums up to the given target sum.
Note: irrelevant link removed by moderator as spam.