Complete search
Complete search (brute force) means enumerating all candidates from a finite search space and choosing those that satisfy a condition / optimize a value.
Given items (), a subset can be represented by a bitmask where bit indicates whether item is chosen. Number of subsets: .
A permutation is an ordering of elements. Number of permutations: .
For each mask from to :
Recursive function at index :
Build the permutation position by position:
Given integers and target , determine if there exists a subset whose sum equals .
Given non-negative integers and , count how many subsets have sum .
Given cities and a complete distance matrix , find the minimum cost of a route that starts at city , visits every city exactly once, and ends anywhere.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long T;
cin >> n >> T;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int total = 1 << n;
for (int mask = 0; mask < total; mask++) {
long long sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) sum += a[i];
}
if (sum == T) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
long long n, S;
vector<long long> a;
long long ans = 0;
void rec(int i, long long sum) {
if (sum > S) return;
if (i == (int)n) {
ans++;
return;
}
rec(i + 1, sum); // skip
rec(i + 1, sum + a[i]); // take
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> S;
a.resize(n);
for (int i = 0; i < (int)n; i++) cin >> a[i];
rec(0, 0);
cout << ans << "\n";
return 0;
}
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int n;
vector<vector<long long>> d;
vector<int> path;
vector<int> used;
long long best = (1LL << 62);
void rec(int depth, int last, long long cost) {
if (cost >= best) return;
if (depth == n) {
best = min(best, cost);
return;
}
for (int v = 1; v < n; v++) {
if (used[v] == 0) {
used[v] = 1;
rec(depth + 1, v, cost + d[last][v]);
used[v] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
d.assign(n, vector<long long>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> d[i][j];
used.assign(n, 0);
used[0] = 1;
rec(1, 0, 0);
cout << best << "\n";
return 0;
}