Subset sum NP-Completness
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".