Complete Search and Backtracking

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Enumerate all subsets via bitmask to find the maximum sum <= W.
5
// Demonstrates 2^n enumeration and bit operations.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    vector<int> a = {3, 34, 4, 12, 5, 2};
12
    int n = (int)a.size();
13
    int W = 10; // capacity/limit
14
15
    long long best = 0; // best feasible sum so far
16
17
    // There are 2^n masks; each mask picks elements whose bits are 1.
18
    // NOTE: ensure 1ULL << n if n can be >= 31 to avoid overflow.
19
    for (unsigned long long mask = 0; mask < (1ULL << n); ++mask) {
20
        long long sum = 0;
21
        // Accumulate sum of chosen elements.
22
        for (int i = 0; i < n; ++i) {
23
            if (mask & (1ULL << i)) sum += a[i];
24
        }
25
        if (sum <= W) best = max(best, sum);
26
    }
27
28
    cout << "Best sum <= W is: " << best << "\n";
29
    return 0;
30
}
31

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Choose a subset with maximum sum <= W using backtracking + pruning.
5
// We sort descending and use suffix sums as an admissible upper bound.
6
7
long long best;
8
long long Wglob;
9
vector<int> vals;
10
vector<long long> suff; // suff[i] = sum of vals[i..n-1]
11
12
void dfs(int i, long long cur) {
13
    int n = (int)vals.size();
14
15
    // Bound: even if we add everything remaining, can we beat best?
16
    long long maxPossible = cur + (i < n ? suff[i] : 0LL);
17
    if (maxPossible <= best) return; // prune by upper bound
18
19
    // Feasibility: current partial sum must not exceed W
20
    if (cur > Wglob) return; // prune infeasible branch
21
22
    // If all elements considered, update best
23
    if (i == n) {
24
        best = max(best, cur);
25
        return;
26
    }
27
28
    // Heuristic: try including vals[i] first (often reaches good solutions earlier)
29
    dfs(i + 1, cur + vals[i]); // take
30
    dfs(i + 1, cur);           // skip
31
}
32
33
int main() {
34
    ios::sync_with_stdio(false);
35
    cin.tie(nullptr);
36
37
    vector<int> a = {3, 34, 4, 12, 5, 2};
38
    Wglob = 10;
39
40
    // Sort descending so suff[i] is a tighter bound (bigger early values)
41
    vals = a;
42
    sort(vals.begin(), vals.end(), greater<int>());
43
44
    int n = (int)vals.size();
45
    suff.assign(n + 1, 0);
46
    for (int i = n - 1; i >= 0; --i) suff[i] = suff[i + 1] + vals[i];
47
48
    best = 0;
49
    dfs(0, 0);
50
51
    cout << "Best sum <= W with pruning: " << best << "\n";
52
    return 0;
53
}
54

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Generate all unique permutations of a multiset (string with duplicates).
5
// Key idea: sort and skip duplicates when the previous identical element
6
// has not been used yet at the current depth.
7
8
string s;
9
vector<int> used;
10
string cur;
11
vector<string> out;
12
13
void backtrack() {
14
    if ((int)cur.size() == (int)s.size()) {
15
        out.push_back(cur);
16
        return;
17
    }
18
    for (int i = 0; i < (int)s.size(); ++i) {
19
        if (used[i]) continue;
20
        // Skip duplicates: if s[i] == s[i-1] and s[i-1] not used,
21
        // then placing s[i] now would duplicate the permutation where s[i-1] was chosen here.
22
        if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue;
23
24
        used[i] = 1;
25
        cur.push_back(s[i]);
26
        backtrack();
27
        cur.pop_back();
28
        used[i] = 0; // undo choice
29
    }
30
}
31
32
int main() {
33
    ios::sync_with_stdio(false);
34
    cin.tie(nullptr);
35
36
    s = "aabc"; // multiset of characters
37
    sort(s.begin(), s.end()); // required for duplicate-skipping rule
38
    used.assign(s.size(), 0);
39
    backtrack();
40
41
    cout << "Count: " << out.size() << "\n";
42
    // Print first few permutations as a demo
43
    for (int i = 0; i < (int)min<size_t>(10, out.size()); ++i) cout << out[i] << '\n';
44
    return 0;
45
}
46

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solve N-Queens using three bitmasks: columns, diag1, diag2.
5
// We also record one board to display a solution, while counting all solutions.
6
7
struct Solver {
8
    int n;
9
    uint64_t full;      // mask with n lowest bits set to 1
10
    uint64_t cols = 0;  // occupied columns
11
    uint64_t d1 = 0;    // diag1 (r-c) shifted: use left-shift on recursion
12
    uint64_t d2 = 0;    // diag2 (r+c): use right-shift on recursion
13
    long long ways = 0; // number of solutions
14
    vector<int> pos;    // pos[r] = column of queen in row r (for one solution)
15
    bool saved = false;
16
17
    void dfs(int r) {
18
        if (r == n) {
19
            ++ways;
20
            if (!saved) saved = true;
21
            return;
22
        }
23
        // available positions for row r: free columns and diagonals
24
        uint64_t available = full & ~(cols | d1 | d2);
25
        while (available) {
26
            // pick least significant 1-bit
27
            uint64_t p = available & -available;
28
            available -= p;
29
            int c = __builtin_ctzll(p); // column index
30
31
            // place queen: update masks; for next row, diagonals shift
32
            cols ^= p;
33
            d1 = (d1 | p) << 1;
34
            d2 = (d2 | p) >> 1;
35
36
            if (!saved) pos[r] = c; // record one solution
37
            dfs(r + 1);
38
39
            // undo changes
40
            d1 >>= 1;
41
            d2 <<= 1;
42
            cols ^= p;
43
        }
44
    }
45
46
    void run(int N) {
47
        n = N;
48
        full = (n == 64) ? ~0ULL : ((1ULL << n) - 1ULL);
49
        pos.assign(n, -1);
50
        dfs(0);
51
52
        cout << "Number of solutions for N=" << n << ": " << ways << "\n";
53
        if (saved) {
54
            cout << "One solution:\n";
55
            for (int r = 0; r < n; ++r) {
56
                for (int c = 0; c < n; ++c) cout << (pos[r] == c ? 'Q' : '.') ;
57
                cout << '\n';
58
            }
59
        }
60
    }
61
};
62
63
int main() {
64
    ios::sync_with_stdio(false);
65
    cin.tie(nullptr);
66
67
    Solver s;
68
    s.run(8); // classic 8-Queens
69
    return 0;
70
}
71