Repository: bitcoin/bitcoin
File: src/wallet/test/fuzz/coinselection.cpp (C++)

Code before:

        AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
        max_spendable += eff_value;

        auto output_group = OutputGroup(coin_params);
        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0);
        group_pos.push_back(output_group);
    }
    size_t num_groups = group_pos.size();
    assert(num_groups <= max_output_groups);

    // Only choose targets below max_spendable
    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_cost_of_change))};

    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
    std::vector<uint32_t> solutions;
    int best_waste{std::numeric_limits<int>::max()};
    int best_weight{std::numeric_limits<int>::max()};
    for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
        // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.
        // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.
        bool is_superset = false;
        for (uint32_t sol : solutions) {
            if ((pattern & sol) == sol) {
                is_superset = true;
                continue;
            }
        }
        if (is_superset) {
            continue;
        }

        CAmount subset_amount{0};
        CAmount subset_waste{0};
        int subset_weight{0};
        for (unsigned i = 0; i < num_groups; ++i) {
            if ((pattern >> i) & 1) {
                subset_amount += group_pos[i].GetSelectionAmount();
                subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;
                subset_weight += group_pos[i].m_weight;
            }
        }
        if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {
            solutions.push_back(pattern);
            // Add the excess (overselection that gets dropped to fees) to waste score
            CAmount excess = subset_amount - target;
            subset_waste += excess;
            SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);

            for (unsigned i = 0; i < num_groups; ++i) {
                if ((pattern >> i) & 1) {

Review comment (suggestion):
13288708523518b72663cbd257dcb7608025126b: Once this is a superset, we could `break`.

```suggestion
                break;
```

Code after:

        AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
        max_spendable += eff_value;

        auto output_group = OutputGroup(coin_params);
        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0);
        group_pos.push_back(output_group);
    }
    size_t num_groups = group_pos.size();
    assert(num_groups <= max_output_groups);

    // Only choose targets below max_spendable
    const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_cost_of_change))};

    // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
    std::vector<uint32_t> solutions;
    int best_waste{std::numeric_limits<int>::max()};
    int best_weight{std::numeric_limits<int>::max()};
    for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
        // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.
        // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.
        bool is_superset = false;
        for (uint32_t sol : solutions) {
            if ((pattern & sol) == sol) {
                is_superset = true;
                break;
            }
        }
        if (is_superset) {
            continue;
        }

        CAmount subset_amount{0};
        CAmount subset_waste{0};
        int subset_weight{0};
        for (unsigned i = 0; i < num_groups; ++i) {
            if ((pattern >> i) & 1) {
                subset_amount += group_pos[i].GetSelectionAmount();
                subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;
                subset_weight += group_pos[i].m_weight;
            }
        }
        if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {
            solutions.push_back(pattern);
            // Add the excess (overselection that gets dropped to fees) to waste score
            CAmount excess = subset_amount - target;
            subset_waste += excess;
            SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);

            for (unsigned i = 0; i < num_groups; ++i) {
                if ((pattern >> i) & 1) {