1279. The Most Groups You Can Take Without Sharing

k groups over n items are given, each as a mask. Choose as many of them as possible so that no two chosen groups share an item. Print how many you can take. Empty groups may not be chosen.

n=3 groups 1 2 4 -> 3 001, 010, 100 are pairwise disjoint n=3 groups 5 2 -> 2 101 and 010 n=3 groups 7 -> 1 n=4 groups 3 12 5 10 -> 2 0011 with 1100; 0101 and 1010 clash with those

The chosen groups do NOT have to cover everything, which is what separates this from #1277.

## What most people try first

Greedy: sort the groups by size and take each one that still fits. Taking the LARGEST first is wrong, and the counterexample is three groups long. With n = 3 and groups 111, 001, 010, largest-first takes 111, which shares an item with everything else, and stops at 1. The optimum takes 001 and 010 for 2. That input is a declared test and the largest-first version was run on it to confirm it answers 1.

Taking the smallest first is a better heuristic and is also not optimal, for a reason that is not about any particular input: this is maximum set packing, which is NP-hard in general, so no fixed ordering rule can be optimal on every instance. What makes an exact method affordable here is the small bound on n, not any property of the ordering.

Every subset of the groups is O(2^k) and k reaches 200000.

## State on the union, not on the index

best[m] = the most groups whose disjoint union is EXACTLY m, or "unreachable" if m is not an exact disjoint union at all best[0] = 0

The transition is #1277's with the objective flipped: decide which chosen group covers one particular item of m, which must be a non-empty available submask s, and the rest of m must itself be an exact disjoint union:

best[m] = max over non-empty available submasks s of m, where best[m ^ s] is reachable, of best[m ^ s] + 1

The answer is the largest best[m] over ALL masks, not best[full]. That is the whole difference from #1277: coverage is not required, so the best packing may leave items untouched, and asking only about the full mask would return "unreachable" on the very first sample.

## Why reachability has to be tracked separately

A mask that is not an exact disjoint union is different from one whose best is 0. Only the empty mask has a best of 0. If unreachable masks were stored as 0 instead, then best[m ^ s] + 1 would read 1 from a mask that cannot be built, and the count would inflate. On n = 3 with the single group 111, mask 011 is unreachable; storing it as 0 would make best[111] consider best[011] + 1 = 1 by way of s = 100, which is not even available, but the same mistake with an available singleton produces a genuinely wrong answer. The reference uses -1 for unreachable and tests for it.

## Collapsing the groups first

As in #1277, k can be far larger than 2^n, so reduce the groups to a presence flag per mask before the DP. Duplicates are irrelevant here, since taking the same mask twice would share every one of its items, so a flag is enough and no count is needed.

## Cost

O(3^n + k), which at n = 12 is 531441 submask steps. The bound is 12 for #1271's reason: 3^20 is 3486784401, too many for a reference solution that must also run in Python.

## Width

Masks are below 2^12 = 4096, so every index fits in a signed 32-bit integer and JavaScript's bitwise operators are safe on plain Numbers. The answer is at most n = 12, since the chosen groups are disjoint and non-empty, so it fits in any integer type at all. Nothing in this problem needs 64 bits and nothing can overflow at any width.

Constraints - `1 ≤ n ≤ 12` - `1 ≤ k ≤ 200000` - `0 ≤ each mask ≤ 2^n - 1`