| Subset Sum Problem in Java [message #1860679] |
Fri, 25 August 2023 00:06  |
Eclipse User |
|
|
|
Hi everyone,
I am working on the Subset Sum Problem in Java. I have found a solution using a recursive approach, but I am wondering if there is a more efficient way to solve it.
The problem is defined as follows:
Given an array of non-negative integers and an integer sum, find whether any subset exists in an array whose sum equals the given integer sum.
For example, given the array [1, 2, 3, 4, 5] and the sum 10, there are two possible subsets that satisfy the problem: [1, 5] and [2, 3, 4].
Here is my recursive solution in Java:
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])
This solution works, but it is not very efficient. Can anyone suggest a more efficient way to solve the Subset Sum Problem in Java?
Thanks in advance for your help!
Sources:
https://www.interviewbit.com/blog/subset-sum-problem/
https://github.com/aravindhrs-lab/ADA-1BM18CS145
|
|
|
|
Powered by
FUDForum. Page generated in 0.25187 seconds
Home