Backtracking

Backtracking is a technique that explores all possible solutions to a problem. It builds solutions step by step and undoes choices whenever it finishes exploring a particular direction.

How It Works

A backtracking algorithm starts with an empty solution. In each step the algorithm goes recursively trying every possible step. After exploring all steps backtrack to the previous step by undoing a choice. The algorithm can be summarized as follows

1. Begin with an empty solution.
2. Extend the solution step by step.
3. Recursively explore all different ways the solution can be constructed.
4. Undo the last step done.

Generating Subsets

To generate all subsets of a sequence using backtracking, start with an empty solution. At each step, consider index i and try both possibilities: include a[i] in the subset or exclude it. After exploring each choice, undo the change. When i moves past the end of the sequence, record the current subset. An example of a code that prints all possible subsets is shown as follows:

#include <iostream>
#include <vector>

using namespace std;

int n = 3;
int a[3] = {5, 3, 1};
vector<int> v;

void backtracking(int i) {

    // if i == n, all the elements are considered, print the current subset
    if (i == n) {
        cout << "subset: ";
        for (int j = 0; j < v.size(); j++) {
            cout << v[j] << ' ';
        }
        cout << "\n";
        return;
    }

    // try when a[i] is included
    v.push_back(a[i]);   // add it to v
    backtracking(i + 1); // try all possible solutions where a[i] is in v

    // try when a[i] is excluded
    v.pop_back();        // undo the step of adding a[i]
    backtracking(i + 1); // try all possible solutions where a[i] is not in v

    // no undo needed because we didn't add anything
}

int main() {

    backtracking(0);
}

Example Problem

Apple Division

Apple Division

CSES

Given array p of n elements. We want to divide elements into two groups such that the absolute difference of the sums of each group is as small as possible. You are asked to print the minimum difference.

Solution

We’ll use backtracking to try every possible grouping and print the one with minimum difference

#include <iostream>

using namespace std;

int n;
int a[20];
long long sum1 = 0;         // sum of the first group
long long sum2 = 0;         // sum of the second group
long long ans = 2000000000; // very large number initially

void backtracking(int i) {
    // if i exceededs the array, update the solution so far
    if (i == n) {
        ans = min(ans, abs(sum1 - sum2));
        return;
    }
    //try all possible choices

    // try to include a[i] in group1
    sum1 += a[i];
    backtracking(i + 1);
    sum1 -= a[i];

    // try to include a[i] in group2
    sum2 += a[i];
    backtracking(i + 1);
    sum2 -= a[i];

}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    backtracking(0);

    cout << ans << "\n";
}