Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I know that the subset sum problem is NP-Complete because I can reduce a known NP-Complete problem to subset sum.
However, since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete. I then realized that the dynamic programming solution in fact tries all possible combinations and because of this, is in fact the same as a brute force approach. Is this a valid insight into why subset sum is NP-Complete?
tries all possible combinations and because of this, is in fact the same as a brute force approach
You don't share the specific algorithm you have in mind, but I think you are wrong. Trying all splittings at every level of the recursion is not the same as trying all solutions.
since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete
Again, you don't share the specific algorithm, but it probably has pseudo-polynomial running time. So no, there is no contradiction; "dynamic programming" does not equal "polynomial time" let alone "fast".
