Structural balance theory (SBT) has maintained a venerable status in the psychological literature for more than 5 decades. One important problem pertaining to SBT is the approximation of structural or generalized balance via the partitioning of the vertices of a signed graph into "K" clusters. This "K"-balance partitioning problem also has more general psychological applications associated with the analysis of similarity/dissimilarity relationships among stimuli. Accordingly, "K"-balance partitioning can be gainfully used in a wide variety of SBT applications, such as attraction and child development, evaluation of group membership, marketing and consumer issues, and other psychological contexts not necessarily related to SBT. We present a branch-and-bound algorithm for the "K"-balance partitioning problem. This new algorithm is applied to 2 synthetic numerical examples as well as to several real-world data sets from the behavioral sciences literature. (Contains 6 tables and 4 figures.)