Suppose you are given an integer array arr. The goal is to split it into the fewest possible subsets such that every pair of elements inside the same subset is coprime (their greatest common divisor equals 1).

We can solve this problem using a DFS backtracking approach. Below are two distinct strategies, each corresponding to a different way of organizing the search space.

Strategy 1: Iterate over Groups

In this version, we decide which elements belong to each group. We maintain a two-dimensional array group to store partitioned elements and a boolean array placed to mark which numbers have already been assigned. The recursion tracks the current group index gid, the position inside that group pos, the starting index in the original array for efficiency, and the count of placed elements.

#include <iostream>
#include <numeric>
#include <vector>

const int MAXN = 12;
int arr[MAXN];
int group[MAXN][MAXN];
bool placed[MAXN];
int total, best;

inline bool coprime_group(const int grp[], int len, int val) {
    for (int i = 0; i < len; ++i) {
        if (std::gcd(grp[i], val) > 1) return false;
    }
    return true;
}

void dfs_by_group(int gid, int pos, int start, int done) {
    if (gid >= best) return;
    if (done == total) {
        best = gid;
        return;
    }
    bool need_new = true;
    for (int i = start; i < total; ++i) {
        if (!placed[i] && coprime_group(group[gid], pos, arr[i])) {
            placed[i] = true;
            group[gid][pos] = arr[i];
            dfs_by_group(gid, pos + 1, i + 1, done + 1);
            placed[i] = false;
            need_new = false;
        }
    }
    if (need_new) {
        dfs_by_group(gid + 1, 0, 0, done);
    }
}

int main() {
    std::cin >> total;
    for (int i = 0; i < total; ++i) std::cin >> arr[i];
    best = total;
    dfs_by_group(1, 0, 0, 0);
    std::cout << best << "\n";
}

Strategy 2: Iterate over Elements

Here we take each element in order and try to insert it into an existing group, or create a brand-new group for it. The recursion depth equals the number of elements processed. We keep the groups in a vector of vectors and maintain a global count of active groups (groups_active). If an element cannot fit into any existing group, it starts a new one. Backtracking restores the previous state.

The critical point that caused the infinite recursion mentioned in the original problem was the misuse of the flag variable combined with zushu++. If an element could fit into multiple existing groups, the condition flag remained false, and the "create new group" branch was skipped, which is correct. However, the original code contained a logic error that sometimes forced new group creation even when unnecessary, and if flag didn't reflect the actual fit correctly, the recursion kept opening new groups endlessly. The corrected version below ensures each element is tried in all possible existing groups, and also in a new group, avoiding an uncontrolled increment of groups_active.

#include <iostream>
#include <vector>
#include <numeric>

int values[12];
std::vector<int> buckets[12];
int n, groups_active = 0, answer;

bool compatible(int bucket_idx, int num) {
    for (int x : buckets[bucket_idx]) {
        if (std::gcd(x, num) != 1) return false;
    }
    return true;
}

void search(int idx) {
    if (idx == n) {
        answer = std::min(answer, groups_active);
        return;
    }
    for (int b = 0; b < groups_active; ++b) {
        if (compatible(b, values[idx])) {
            buckets[b].push_back(values[idx]);
            search(idx + 1);
            buckets[b].pop_back();
        }
    }
    buckets[groups_active].push_back(values[idx]);
    ++groups_active;
    search(idx + 1);
    --groups_active;
    buckets[groups_active].pop_back();
}

int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> values[i];
    answer = n;
    groups_active = 0;
    search(0);
    std::cout << answer << "\n";
}

Intuitive Comparison

Both strategies model the same combinatorial problem but traverse the decision tree differently. The first is like taking an empty bin and trying to fill it with as many compatible items as possible before moving to the next bin. The second is like going through the items sequentially and, for each item, either placing it in an already open bin or opening a new one.

Neither approach is inherently superior; they just organize the backtracking state in complementary ways. The key to avoiding infinite loops is ensuring that the recursion always makes progress (the number of placed items increases) and that backtracking correctly restores state without leaking side effects like untracked group counts.