Brute force

Brute force solves a problem by trying every possible answer and checking each one. It works when there are few enough possible answers to try them all within the time limit. It also helps test a faster solution: run both programs on many small random inputs and compare their answers.

Explanation

A shop sells pens for 3 coins and notebooks for 5. In how many ways can you spend exactly 15 coins? You can buy 0 to 5 pens and 0 to 3 notebooks, so there are 6 · 4 = 24 baskets.

Fig. 1. Every basket is one cell: the number of pens is above it, the number of notebooks on the left, and the basket's cost inside. The green baskets cost exactly 15.

Each basket is a candidate, a possible answer. Brute force lists every candidate (enumerate), tests it (check), and adds 1 for each one that passes or keeps the best (record). The answer is right because no basket is skipped. In code, this is two nested loops.

Computing the last unknown

One loop is enough here. After the pens, all the money left goes on notebooks, so it must be a multiple of 5.

Fig. 2. One check per number of pens (above each cell). The money left must be a multiple of 5, and the number of notebooks under it is computed.

That is 6 checks instead of 24, with the same 2 baskets. When the last unknown is fixed by the others, compute it instead of looping over it.

Counting before you code

A rule of thumb says a computer does about 10^8 simple steps per second (see time complexity), so count the candidates before writing the loops. With 10^4 coins, you can buy 0 to 3333 pens and 0 to 2000 notebooks: 3334 · 2001, about 6.7 \cdot 10^6 checks, well under a second. Now the shop also sells erasers for 7 coins, and a third loop tries 0 to 1428 erasers. That makes 3334 · 2001 · 1429, about 9.5 \cdot 10^9 checks: around 95 seconds. Computing the erasers instead brings it back to two loops.

Three items a, b, c give 2 · 2 · 2 = 8 subsets: {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c} and {a, b, c}. Each of $n$ items is either taken or not, so there are 2^n subsets. The same three items can be lined up in 3 · 2 · 1 = 6 orders: abc, acb, bac, bca, cab and cba. An order is also called a permutation. With $n$ items there are $n$ choices for the first place, n - 1 for the second, and so on, so there are n! = 1 \cdot 2 \cdots n orders.

The table counts the candidates of each common kind and gives the largest $n$ that fits in about 10^8 steps.

In C++

// count first: candidates × cost of one check, about 10^8 per second
long long answer = 0;               // or best = a very large number
for (/* every candidate c */)       // enumerate
    if (/* c passes the check */)   // check
        answer++;                   // record (or best = min(best, cost of c))

Pairs and triples

To count the pairs of elements with sum s, the outer loop picks a[i] and the inner loop a[j]. Starting j at i + 1 lists each of the n(n-1)/2 pairs once and never pairs an element with itself. A third loop with k from j + 1 lists the triples.

The input is n and s, then n numbers, read into an array (here a vector):

6 10
3 8 5 2 7 6

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long cnt = 0;
    for (int i = 0; i < n; i++)          // enumerate: every pair i < j
        for (int j = i + 1; j < n; j++)
            if (a[i] + a[j] == s)        // check
                cnt++;                   // record
    cout << cnt << '\n';
}

All subsets

A subset of n items can be written as a number mask from 0 to 2^n - 1: item i is taken when bit i of mask is 1. The expression mask >> i & 1 moves bit i to the last place and keeps only that bit (bitmasks explains these operators). 13 = 8 + 4 + 1 is 001101 in binary: bits 3, 2 and 0 are 1, so mask = 13 takes items 0, 2 and 3.

Fig. 3. Bit i of the mask says whether item i is taken. These are the 3 of the 64 masks whose items add up to 10.

1 << n is 1 followed by n zero bits, that is 2^n. One loop over mask goes through all 2^n subsets, and an inner loop over i reads each one: O(2^n \cdot n), fine up to about n = 20.

This program counts the subsets with sum s on the same input.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long cnt = 0;
    for (int mask = 0; mask < (1 << n); mask++) {   // enumerate: every subset
        long long sum = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) sum += a[i];         // item i is taken
        if (sum == s)                               // check
            cnt++;                                  // record
    }
    cout << cnt << '\n';
}

All orders

Three workers must do three jobs, one each, and worker i doing job j costs c[i][j]. A candidate is an order of the jobs p, where p[i] is the job of worker i. next_permutation(p.begin(), p.end()) turns p into the order that comes next in a dictionary (0 1 2, 0 2 1, 1 0 2, …) and returns false when p was already the last one. A do … while loop runs its body before the first call to next_permutation, so the starting order is checked too. Started from 0 1 2, the loop visits all $n!$ orders.

Fig. 4. The loop visits the 6 orders from 0 1 2 to 2 1 0. Under each order is its total cost, and under that the smallest total so far, green where it drops. The cheapest order, 1 2 0, costs 8.

The loop only moves forward, so it never visits the orders before its start. Call sort on p first when it is not sorted.

The input is n, then n rows of costs, one per worker:

3
1 2 6
2 9 3
3 8 9

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> c(n, vector<int>(n));   // a table: n rows of n costs
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> c[i][j];

    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;   // p[i] is the job of worker i; 0 1 2 ... is sorted

    long long best = 1e18;                  // larger than any total
    do {                                    // enumerate: every order
        long long total = 0;
        for (int i = 0; i < n; i++) total += c[i][p[i]];   // check: cost of this order
        best = min(best, total);            // record
    } while (next_permutation(p.begin(), p.end()));
    cout << best << '\n';
}

Common mistakes

• Counting every pair twice, or pairing an element with itself. With j starting at 0, the array 3 8 5 2 7 6 and s = 10 give 5 instead of 2: (3, 7), (7, 3), (8, 2), (2, 8) and 5 with itself.

• Using a shortcut rule without proof when $n$ is small enough to try every candidate. For the workers above, letting each in turn take the cheapest free job costs 1 + 3 + 8 = 12, but the cheapest order costs 8, so try all orders whenever n! \cdot n fits.

Similar techniques

• Backtracking builds a candidate one choice at a time and drops it as soon as it breaks a rule, instead of checking whole candidates at the end.

• Recursion lists candidates when the number of nested loops would depend on the input.

• Meet in the middle handles about 40 items by trying all subsets of each half and combining them.

• Dynamic programming handles too many candidates that share parts, solving each part once.

• Greedy algorithms make one choice per step, like the cheapest-free-job rule above, and need a proof.

• Two pointers find pairs with a given sum in a sorted array in $O(n)$.

Practice