【正经题解】背包问题

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;  // 最大物品数量

int weights[MAX_N];       // 每件物品的重量
int selectedWeights[MAX_N];  // 被选中的物品重量
int itemCount, targetWeight;
bool solutionFound = false;

// 深度优先搜索函数
void dfs(int depth, int selectedCount, int currentWeight) {
    if (currentWeight == targetWeight) {
        // 输出找到的解
        for (int i = 1; i <= selectedCount; i++) {
            cout << selectedWeights[i] << " ";
            solutionFound = true;
        }
        cout << endl;  // 换行
        return;
    } else {
        // 递归搜索
        if (currentWeight > targetWeight || depth > itemCount || solutionFound == true) return;
        selectedWeights[selectedCount + 1] = weights[depth];
        dfs(depth + 1, selectedCount + 1, currentWeight + weights[depth]);
        dfs(depth + 1, selectedCount, currentWeight);
    }
}

int main() {
    // 输入物品数量和目标重量
    cin >> itemCount >> targetWeight;

    // 输入每件物品的重量
    for (int i = 1; i <= itemCount; i++) {
        cin >> weights[i];
    } 

    // 开始深度优先搜索
    dfs(1, 0, 0);

    // 输出结果或"No Answer!"
    if (!solutionFound) {
        cout << "No Answer!" << endl;  // 换行
    }

    return 0;
}