A well-known problem is studied of the number of repetition-free words of the two types: the square-free words over a three-letter alphabet and the cube-free words over a two-letter alphabet.

We obtain an exact upper bound on the complexity of solving the Subset Sum problem with a variation of the branch-and-bound method of a special form. Complexity is defined as the number of subproblems considered in the process of solving the original problem. Here we reduce the enumeration by using the domination relation. We construct an instance of the Subset Sum problem on which our bound is realized. The resulting bound is asymptotically twice smaller than the exact upper bound on the complexity of solving this problem with a standard version of the branch-and-bound method.

The paper is concerned with estimating the computational complexity of the branch-and-bound method for the subset sum problem. We study the relationship between the way of decomposition of subproblems and the number of the method steps. The standard variant of the branch-and-bound method for the subset sum problem with binary branching is considered: any subproblem is decomposed into two more simple subproblems by assigning values 0 and 1 to a selected branching variable. It is shown that for any set of parameters of the problem the procedure of branching variables selection in the descending order of their weights is optimal.