题解 | #称砝码#

本题需要求能称出多少种重量，可以转化为求子集问题，求子集可以用回溯法实现，但是求出的子集中，某些子集和可能相等，因此还要进一步去重，可以考虑利用set保存子集达到去重的目的。

#include<iostream>
#include<unordered_set>
#include<vector>
#include<algorithm>
using namespace std;
int sum = 0;
unordered_set<int> res;
void backTrack(const vector<int>& input, int beg);
int main(){
    int n = 0;
    while(cin >> n){
        vector<int> weight;
        vector<int> count;
        int a;
        for(int i = 0; i < n; ++i){
            cin >> a;
            weight.push_back(a);
        }
        for(int i = 0; i < n; ++i){
            cin >> a;
            count.push_back(a);
        }
        vector<int> input;
        for(int i = 0; i < weight.size(); ++i){
            for(int j = 0; j < count[i]; ++j){
                input.push_back(weight[i]);
            }
        }
        sort(input.begin(), input.end());
        backTrack(input, 0);
        cout << res.size() << endl;
        sum = 0;
        res.clear();
    }
}
//回溯法实现求解子集
void backTrack(const vector<int>& input, int beg){
    res.insert(sum);
    for(int i = beg; i < input.size(); ++i){
        if(i > beg && input[i] == input[i - 1])
            continue;
        sum += input[i];
        backTrack(input, i + 1);
        sum -= input[i]; //回溯
    }
}