Web Development·12,149 discussions

[kees_b]

Subset Sum Problem in Java

Tags: Web development

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.

• This topic was modified 1 year, 8 months ago by kees_b.

Topic

Re: problem

In reply to Subset Sum Problem in Java

That’s strange. You’re trying to solve a problem, you found a solution, your tell what it does (“means that there is a subset of the given array that sums up to the given target sum.”) and then you ask what it does (“What does the subset_sum() function do?”).

I

Explanation of the code

In reply to Subset Sum Problem in Java

The subset_sum() function takes three parameters:

1. set: An array of integers
2. n: The number of elements in the array
3. sum: The target sum

The function works by recursively trying all possible combinations of elements from the array to see if they add up to the target sum.

The base cases are:

1. If the target sum is 0, then the function returns True, because any subset of the array will sum up to 0.
2. If the number of elements is 0, then the function returns False, because there are no elements to choose from.

Otherwise, the function does the following:

1. It checks if the last element in the array is greater than the target sum. If it is, then the function recursively calls itself to find a subset of the remaining elements that sums up to the target sum.
2. Otherwise, the function recursively calls itself twice:
Once to find a subset of the remaining elements that sums up to the target sum, without including the last element.
Once to find a subset of the remaining elements that sums up to the target sum, including the last element.

The recursive call works by passing the remaining elements of the array, the number of remaining elements, and the updated target sum to the subset_sum() function.

The time complexity of the algorithm is O(2^n), where n is the number of elements in the array. This is because the number of possible subsets of an n-element array is 2^n.

The space complexity of the algorithm is O(n), because the function needs to store the remaining elements of the array in memory.

I hope this explanation is helpful.

[Author]

Replies