Possible is not enough
Decidable problems can be solved — eventually. Complexity theory asks how long it takes. The class P holds problems solvable in polynomial time: n, n², n³ steps for an input of size n. Sorting, shortest paths and running a DFA are all in P. Exponential time, 2ⁿ steps, is different in kind: adding one item doubles the work, and n = 100 already takes longer than the age of the universe.
Some problems seem to need exponential search yet have answers that are easy to check. Given numbers and a target, finding a subset that adds up to the target may mean trying all 2ⁿ subsets — but if someone hands you a subset, adding it up takes a moment. Problems like that form the class NP, and whether P = NP is the most famous open question in computer science, with a million-dollar Clay prize attached.
Certificates and verifiers
A problem is in NP when every yes-instance has a certificate — a proposed solution — that a verifier can check in polynomial time. For subset sum the certificate is a list of indexes; the verifier checks they're distinct and in range and that the numbers add to the target. A bad certificate must be rejected, so validation matters as much as the arithmetic.
verifySubsetSum([3, 34, 4, 12, 5, 2], 9, [2, 4]) // 4 + 5 = 9 → true verifySubsetSum([3, 34, 4, 12, 5, 2], 9, [2, 2]) // repeats index 2 → false
Solving by brute force is just "try every certificate and verify it". Loop a bitmask from 0 to 2ⁿ − 1; bit i set means pick item i.