Basics 0/97

Complete search: enumerating candidate solutions · 3 of 3

Subsets and permutations

Loop over every subset with a bit mask and over every ordering with the library, without counting a repeated string twice.

2,707 words · 13 min read

Part 1 of 6 Every subset

A search over every subset

Nested loops suit a candidate made of a fixed number of choices. In many problems a candidate is instead a group of the items, of any size: the apples that go into one bag, the coins used for a payment, the tasks we decide to take on. Such a group is a subset of the items, and nn items have 2n2^n subsets, because each item is either in the group or out of it. The next problem is a search of this kind.

You have nn apples with known weights. Divide them into two groups so that the difference between the groups' total weights is as small as possible, and print that difference.

The first input line holds nn, and the second holds the weights p1,p2,…,pnp_1, p_2, \dots, p_n.

Constraints

  • 1≤n≤201 \le n \le 20
  • 1≤pi≤1091 \le p_i \le 10^9

Sample · Input

5
3 2 7 4 1

Output

1

In the sample the weights add up to 17, an odd number, so the two groups cannot weigh the same and a difference of 1 is the best possible. The groups 2+7=92 + 7 = 9 and 3+4+1=83 + 4 + 1 = 8 reach it.

No simple rule finds the best division in general. Giving each apple in turn to the lighter group, for example, divides the weights 3, 3, 2, 2, 2 into groups of 7 and 5, although 3+33 + 3 against 2+2+22 + 2 + 2 is an even split. The limit n≤20n \le 20 says we do not need a rule. A division is fixed by the set of apples in the first group, since the others go to the second, so there are at most 220=1,048,5762^{20} = 1{,}048{,}576 divisions, and a program can try every one.

Three apples could be handled by three nested loops, each choosing a group for one apple. But the number of apples is read from the input, and the number of nested loops in a program cannot depend on its input. So we number the subsets instead, and a single loop over the numbers visits every subset.