In this case, the particle is constrained to a sphere, therefore the natural solution would be to use angular coordinates to describe the position of the particle instead of Cartesian and solve (automatically eliminate) the constraint in that way (the first choice). For pedagogical reasons, instead, consider the problem in (redundant) Cartesian coordinates, with a Lagrange multiplier term enforcing the constraint.