Magic Pocket Subset Sum

The Magic Pocket problem requires determining the number of ways to select items such that their total volume equals exactly 40. This can be approached using a Depth-First Search (DFS) strategy where we explore every possible combination of including or excluding an item. We maintain a running sum of the selected volumes. If the sum matches the target capacity, we increment the solution counter. If the index exceeds the number of items or the sum surpasses the capacity, we backtrack.

#include <iostream>
#include <vector>

int n, total_solutions;
std::vector<int> weights;

void explore_combinations(int item_idx, int current_weight) {
    if (current_weight == 40) {
        total_solutions++;
        return;
    }
    if (item_idx == n || current_weight > 40) return;

    // Include the current item
    explore_combinations(item_idx + 1, current_weight + weights[item_idx]);
    // Exclude the current item
    explore_combinations(item_idx + 1, current_weight);
}

int main() {
    while (std::cin >> n) {
        weights.resize(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> weights[i];
        }
        total_solutions = 0;
        explore_combinations(0, 0);
        std::cout << total_solutions << std::endl;
    }
    return 0;
}

Eight Queens Configuration

The Eight Queens problem asks for all distinct arrangements of eight queens on a chessboard such that no two queens threaten each other. An efficient strategy is to pre-compute all 92 valid solutions using backtracking and store them for quick lookup. We represent the board state as an array where the index represents the row and the value represents the column. To ensure validity, we check if a column is already occupied and verify that no previously placed queen shares a diagonal. Diagonal conflict is detected if the absolute difference between rows equals the absolute difference between columns. Valid configurations are encoded as integers, sorted, and retrieved based on user input.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

const int BOARD_SIZE = 8;
std::vector<int> valid_configurations;
int placement[BOARD_SIZE]; // placement[row] = col
bool is_col_used[BOARD_SIZE] = {false};

void solve_n_queens(int current_row) {
    if (current_row == BOARD_SIZE) {
        int encoded_val = 0;
        for (int r = 0; r < BOARD_SIZE; ++r) {
            encoded_val = encoded_val * 10 + (placement[r] + 1); // 1-based columns for encoding
        }
        valid_configurations.push_back(encoded_val);
        return;
    }

    for (int col = 0; col < BOARD_SIZE; ++col) {
        if (is_col_used[col]) continue;

        bool is_safe = true;
        for (int prev_row = 0; prev_row < current_row; ++prev_row) {
            int prev_col = placement[prev_row];
            if (std::abs(current_row - prev_row) == std::abs(col - prev_col)) {
                is_safe = false;
                break;
            }
        }

        if (is_safe) {
            placement[current_row] = col;
            is_col_used[col] = true;
            solve_n_queens(current_row + 1);
            is_col_used[col] = false;
        }
    }
}

int main() {
    solve_n_queens(0);
    std::sort(valid_configurations.begin(), valid_configurations.end());

    int query_count;
    while (std::cin >> query_count) {
        while (query_count--) {
            int k;
            std::cin >> k;
            std::cout << valid_configurations[k - 1] << std::endl;
        }
    }
    return 0;
}