| Subset Sum Problem in Java [message #1860679] |
Fri, 25 August 2023 04:06  |
 Ashley coder
Messages: 11
Registered: October 2022 |
Junior Member |
|
|
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
|
|
|
| Re: Subset Sum Problem in Java [message #1861050 is a reply to message #1860679] |
Fri, 15 September 2023 14:27  |
|
This really isn't the place for programming questions, it's for questions about the Java IDE. You'd have a better, more general, audience on javaranch.com or stackoverflow.com.
_
Nitin Dahyabhai
Eclipse Web Tools Platform
|
|
|
Powered by
FUDForum. Page generated in 0.03623 seconds
] 
Search
Help
Register
Login
Home
