SRM 622 Div2 L3 Subsets：回溯剪枝求最優子集

問題大意

給定整數數組，選擇子集使 sum + ones_cnt = product，最大化 sum + ones_cnt - product（即超出部分）。1 不影響乘積只加和，優先考慮非 1 元素。

回溯剪枝

• 非 1 元素極少（乘積增長極快），回溯搜尋空間極小。
• 狀態：當前和、乘積、位置。決定加入或跳過（跳過相同值直接跳到下一不同值）。
• 若 sum + ones_cnt > product，更新答案並繼續搜尋（可能更大）。

代碼

class Subsets {
    vector<int> numbers; int ones_cnt, res; int nextdiff[1005];
    void backtrack(int sum, int prod, int pos) {
        int cur = numbers[pos];
        int ns = sum + cur, np = prod * cur;
        if (ns + ones_cnt > np) {
            res += ns + ones_cnt - np;
            if (pos+1 < numbers.size()) backtrack(ns, np, pos+1);
        }
        if (nextdiff[pos] < numbers.size()) backtrack(sum, prod, nextdiff[pos]);
    }
    int findSubset(vector<int> nums) {
        sort(nums.begin(), nums.end());
        numbers = nums;
        int n = nums.size();
        for (int i=0;i