Subsets, Permutations and Bitmask Basics - Язык программирования C++ для спортивного программирования
Subsets, Permutations and Bitmask Basics
Subsets, Permutations and Bitmask Basics
Introduction
Some problems do not ask us to make one deterministic sequence of moves. Instead, we must consider many possible choices: which objects to take, in what order to arrange them, or which decisions produce a valid answer.
When the number of objects is small, exhaustive search is often exactly the intended solution. The key is to understand what kind of objects we are enumerating and how many of them exist.
A subset decides independently whether each element is chosen. A set of n elements has 2n subsets.
A permutation places all n distinct elements in an order. There are n! permutations.
A bitmask stores several yes-or-no decisions inside one integer, making it a natural representation of a subset.
These techniques are basic building blocks for backtracking, bitmask dynamic programming, meet-in-the-middle, and many small-constraint problems.
Choosing the right object to enumerate
Before writing code, ask what one complete candidate answer looks like.
Suppose the objects are [4,7,2].
A subset may be [4,2]. The original relative order is irrelevant; the decision is simply “take or do not take” for each position.
A permutation may be [2,4,7]. Every object is used exactly once, and the order matters.
These are very different search spaces. There are 23=8 subsets but 3!=6 permutations. For n=20, there are about one million subsets, which is often manageable. However, 20! is enormous and cannot be enumerated.
The constraints usually reveal the intended search space. Values around n≤20 often suggest subsets or bitmasks. Values around n≤9 may allow all permutations, depending on the work done for each one.
Subsets by recursion
To generate a subset, process elements from left to right. At position i, there are exactly two choices:
do not include a[i];
include a[i].
After making either choice, recursively process position i+1. When all positions have been decided, the current selection is one complete subset.
The recursive state contains:
the next position i to decide;
the elements currently selected, or another summary such as their sum.
If we store selected elements in a vector, choosing an element means pushing it before the recursive call. After the call returns, we pop it so that the next branch begins from the correct state. This removal is the “backtracking” part.
The empty subset appears when we choose “do not take” at every position. It is a valid subset and should not be forgotten.
Bitmask basics
An integer is stored as binary digits called bits. Each bit is either 0 or 1, exactly like the two choices for one array position.
For subset enumeration, it is natural to use 0-based positions. Bit i represents whether a[i] is selected:
bit i=0: do not take a[i];
bit i=1: take a[i].
For n elements, we use the lowest n bits. Every integer from 0 to 2n−1 gives one different pattern of bits, so it gives one different subset.
For example, with a=[4,7,2]:
mask
binary
chosen positions
subset
0
000
none
[]
1
001
0
[4]
2
010
1
[7]
3
011
0,1
[4,7]
4
100
2
[2]
5
101
0,2
[4,2]
6
110
1,2
[7,2]
7
111
0,1,2
[4,7,2]
The written binary digits are usually shown from the highest bit to the lowest, while array position 0 corresponds to the rightmost bit.
Main bit operations
The expression 1 << i creates a number whose only set bit is bit i.
Check bit i:(mask >> i) & 1, or mask & (1 << i).
Set bit i to 1:mask | (1 << i).
Clear bit i:mask & ~(1 << i).
Toggle bit i:mask ^ (1 << i).
For simple subset enumeration, checking bits is enough. The other operations become useful when a mask is changed or used as a dynamic-programming state.
Use parentheses around shifts in larger expressions. Also remember that 1 << n uses an int. If n may reach or exceed 31, use 1LL << n, although enumerating that many subsets is normally impossible anyway.
[VISUAL IDEA: align the three array cells with bits 0, 1, and 2, then move through masks 000 to 111 while highlighting the selected cells]
Subset problem: best sum under a limit
Suppose we are given n≤20 non-negative numbers and a limit S. We want the largest possible subset sum that does not exceed S.
A greedy choice such as taking the smallest or largest values first is not always correct. We can instead examine every subset. For each mask, add the elements whose bits are set. If the sum is at most S, use it to improve the answer.
There are 2n masks, and checking one mask takes O(n) time. The total complexity is O(n2n), which is practical for n≤20.
Permutations by backtracking
A permutation uses every element exactly once. We build it from left to right.
At position pos, try every value that has not yet been used:
place the value at p[pos];
mark it as used;
recursively fill the next position;
mark it as unused again.
The undo step is essential. After finishing all permutations that begin with one value, we must return that value to the available set before trying the next first value.
The recursion tree has n choices on the first level, n−1 on the second, and so on. It has n! leaves, one for each permutation. Printing all permutations already requires Θ(n⋅n!) time because every printed answer contains n values.
If the input contains equal values, treating positions as distinct can print the same value sequence several times. A common solution is to sort the values and skip equal unused choices on the same recursion level. For the basic algorithm, we assume all values are distinct.
Main algorithms
Algorithm:
Recursive subset generation and bitmask enumeration visit the same 2n candidates in different orders. Choose the representation that makes the work on each subset easiest. Bitmasks are compact and fit naturally into dynamic programming. Recursion is often clearer when choices need pruning or more complicated state changes.
Implementation: best subset sum with a bitmask
The input contains n, a limit S, and n non-negative values. The program prints the largest subset sum not exceeding S.
Implementation: generating permutations
The input contains n≤9. The program prints every permutation of the integers from 1 to n in lexicographic order.
Complexity
Bitmask subset enumeration:O(n2n) time and O(1) additional memory, apart from the input.
Recursive subset generation:O(2n) calls and O(n) recursion depth, plus the cost of processing each subset.
Permutation generation:Θ(n⋅n!) time when all permutations are printed and O(n) recursion memory.
1. Enumerate subsets with bitmasks:
1.1. Set best = 0.
1.2. For mask = 0..(1<<n)-1:
1.2.1. Set sum = 0.
1.2.2. For i = 0..n-1:
1.2.2.1. If bit i of mask is 1, add a[i] to sum.
1.2.3. If sum <= limit, set best = max(best, sum).
2. Define gen_subset(i):
2.1. If i == n:
2.1.1. Process the current subset.
2.1.2. Return.
2.2. Call gen_subset(i+1) without choosing a[i].
2.3. Add a[i] to the current subset.
2.4. Call gen_subset(i+1).
2.5. Remove a[i] from the current subset.
3. Define gen_perm(pos):
3.1. If pos == n+1:
3.1.1. Process p[1..n].
3.1.2. Return.
3.2. For x = 1..n:
3.2.1. If used[x] is true, continue.
3.2.2. Set p[pos] = x and used[x] = true.
3.2.3. Call gen_perm(pos+1).
3.2.4. Set used[x] = false.
#include <bits/stdc++.h>using namespace std;const int N = 25;int n;long long limit_sum;long long a[N];int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> limit_sum; for(int i = 0; i < n; i++){ cin >> a[i];} long long best = 0; int total_masks = 1<< n; for(int mask = 0; mask < total_masks; mask++){ long long sum = 0; for(int i = 0; i < n; i++){ if((mask >> i) & 1){ sum += a[i];}} if(sum <= limit_sum){ best = max(best, sum);}} cout << best << endl; return 0;}
#include <bits/stdc++.h>using namespace std;const int N = 12;int n;int p[N];bool used[N];void gen_perm(int pos){ if(pos == n + 1){ for(int i = 1; i <= n; i++){ cout << p[i]<< ' ';} cout << endl; return;} for(int x = 1; x <= n; x++){ if(used[x]){ continue;} p[pos] = x; used[x] = true; gen_perm(pos + 1); used[x] = false;}}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; gen_perm(1); return 0;}