Amazon Interview Question Software Engineer / Developers
Country: -
if I consider my elements are 5,3,12,1,6 and if i check to see if 25 can be generated .. according to this algorithm it will return true but it shouldn as you cannot repeat the same element more than 2 times to generate the sum .. in this case 25 can only be formed by 12+3+5+5 ... Please correct me if I am wrong ..
Yes there is solutiuon based on dynamic programming and also another technique which runs in O(n*2^(n/2)) check wikipedia for the solutions
Everyone know it's dynamic programming. So what's the solution? At least give a url to a solution?
This is subset sum problem, which is known to be NP complete. So, there is no known solution with complexity better than O(2^n).
The above comment is utterly wrong.
1) It is NP-Hard and not NP-Complete. NP-Complete is reserved for _decision_ problems.
2) Being NP-Hard does mean there can't be better than Theta(2^n) algorithms.
3) There are known O(n sqrt(2^n)) algorithms. See the wiki page and look for Sahni's divide and conquer algorithm.
I guess what you mean is NP but not P
because when you say NP-Hard but not NPC it mean problem is not solvable for all possible inputs.
Plz correct me if i am wrong
@hardbug: You are wrong. NP-Hard means at least as hard as any problem in NP. NP complete means, NP-Hard _and_ in NP. So NP-Complete is a subset of NP-Hard.
NP-Hard does not mean unsolvable/undecideable. There might be NP-Hard problems for which this is true (like Halting problem), but that it not necessarily the case for all.
Deciding if a subset exists which sums to a given number is NP-Complete (decision problem), but actually finding the subset is NP-Hard (it is not a decision problem and so is not in NP).
create a hashmap for each element in the array which takes O(n) and takes the first element subtract it from the number that need to be searched in the array, if it exists in the hashmap then return both the integers, else similarly do for the other elements in the array .. so the total complexity O(2*n) and space complexity is O(N)
Assuming array has n elements, sum should be equal to S.
- sausax September 15, 2011Create a boolean array with S+1 elements, with first element as true rest as false.
for i in (n elem array):
for j in booleanArr:
if booleanArr[j] == true:
booleanArr[j+i] = true
return booleanArr[S]