Question

  • Creator
    Topic
  • #4153307

    Subset Sum Problem in Java

    by RoxenJ ·

    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 Avatar photokees_b.

You are posting a reply to: Subset Sum Problem in Java

The posting of advertisements, profanity, or personal attacks is prohibited. Please refer to our Community FAQs for details. All submitted content is subject to our Terms of Use.

All Answers

  • Author
    Replies
    • #4153428
      Avatar photo

      Re: problem

      by kees_b ·

      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

    • #4157095

      Explanation of the code

      by Harisamer214 ·

      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.

Viewing 1 reply thread