Bunty12 Posted March 5, 2023 Share Posted March 5, 2023 Create an algorithm for the Subset Sum problem that runs in time O(nK) or better. Given a set X = {x1, x2, …, xn} of n integers and another integer K, the algorithm should check if there is a subset X' of X whose elements sum to K and if so, it should find this subset. For example, if X = {5, 3, 11, 8, 2} and K = 16, the algorithm should answer YES since the subset X' = {5, 11} has a sum of 16. I have referred to this code from the issue I'm trying to solve: please stop spamming us with advertising! I believe that utilizing dynamic programming techniques can improve the complexity of the problem from O(nK) to something lower. I have discovered an algorithm that runs in exponential time, but it has not been of any assistance. Is there anyone who can help me with this issue? Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now