Advancement in energy storage technologies has enabled the emergence of new applications, such as grid-scale and domestic energy storage and electric vehicles (EVs). Despite the advances, the loss of energy during operation is one of the major challenges in improving the energy efficiency and the lifetime of storage systems. Reconfigurable energy storage allows the dynamic rearrangement of the unit cells to reduce voltage variations and therefore increase energy efficiency, but the introduction of switching circuit increases the upfront cost of the systems. Therefore, determining the granularity of reconfiguration that achieves high energy efficiency at a reasonable cost is a crucial design decision. However, the design space exploration for finding the optimal granularity often involves time-consuming evaluation of numerous feasible solutions. In this paper, we propose a novel algorithm to accelerate the design space exploration for reconfigurable energy storage in a branch-and-bound manner. The proposed algorithm finds a set of Pareto front solutions in terms of cost and energy efficiency with a reduced amount of computation. We apply the proposed algorithm to the design of supercapacitor energy storage for an EV, and the experimental result shows a reduction in computation by 45.4% on average with only 6.1% of non-Pareto (but still near-optimal) solutions included in the suggested solutions.