Programmable metasurfaces have emerged as a revolutionary technology with the flexibility in manipulating electromagnetic (EM) waves. They have attracted great interest in fields including wireless signal processing, radar, and satellite systems in recent years. Metasurface-based beamforming problem is widely solved by array synthesis techniques. However, traditional analytic and stochastic approaches suffer from limited applicability, low efficiency, and high computational cost. In particular, programmable metasurfaces usually consist of elements with finite states, making the synthesis problem integer and non-deterministic polynomial-time hard (NP-hard). In this paper, we propose a novel beamforming approach for digital-coding metasurfaces based on branch and bound (B&B). The proposed approach enables efficient optimization of amplitude-phase distributions of metasurfaces to synthesize complex beam patterns with specific radiation characteristics. By narrowing down the search space and pruning suboptimal solutions, the approach achieves a balance between global optimality and computational complexity. Moreover, the approach is fit for both space-coding metasurfaces (SCMs) and space-time-coding metasurfaces (STCMs), thus covering a wide range of applications. Full-wave simulations and experimental measurements are conducted to verify the proposed approach. The results demonstrate decent performance, including precise beam steering and low sidelobes. In contrast to traditional works, the proposed approach solves the complex beamforming problem more quickly and efficiently, providing a viable technique for the application of reconfigurable intelligent surfaces in sixth-generation (6G) networks.