1755. 最接近目標值得子序列和

思路

觀察資料範圍，$1\leq{n}\leq40$，
在 $n=20$ 的時候，我們能夠枚舉所有的狀態並檢查，但現在大小翻倍，枚舉會超時。

我們能將答案分為左半邊 + 右半邊 + 橫跨左右兩邊的解。

• 左半邊：直接枚舉出可能的總和。
• 右半邊：同樣枚舉出可能的總和。
• 橫跨左右兩邊的解：左邊選一個總和，右邊選一個總和，這時兩個數字總和會對應到一個「拼接起來」的子序列。

只要對左右半邊加入一個「什麼也不選」的情況，也就是總和為 0，
雙指針計算時，就會一併算到單選左半與右半的情況。

程式碼

1. 折半枚舉（位運算）+ 雙指針

class Solution {
private:
    static const int MX = 40;
    static const int MXSIZE = (1<<20);
    int A[MXSIZE], B[MXSIZE]; // 將數組切成左右兩邊，存放各自產生出的序列，對應的數字總和
    void build(vector<int>& nums, int n, int OFFSET, int part[]) {
        // 枚舉
        for(int i = 0; i < (1 << n); i++) {
            int sum = 0;
            for(int j = 0; j < n; j++) {
                if((i >> j) & 1) {
                    sum += nums[j + OFFSET];
                }
            }
            part[i] = sum;
        }
    }
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        build(nums, n / 2, 0, A);
        build(nums, n - n / 2, n / 2, B);

        sort(A, A + (1 << n / 2));
        sort(B, B + (1 << (n - n / 2)));
        
        // 合併左右，雙指針
        int res = INT_MAX;
        for(int left = 0, right = (1 << (n - n / 2)) - 1; left < (1 << n / 2); left++) {
            while(right >= 0 && A[left] + B[right] >= goal) {
                res = min(res, A[left] + B[right] - goal);
                right--;
            }
        }
        for(int left = 0, right = (1 << (n - n / 2)) - 1; right >= 0; right--) {
            while(left < (1 << n / 2) && A[left] + B[right] <= goal) {
                res = min(res, goal - A[left] - B[right]);
                left++;
            }
        }
        return res;
    }
};

2. 折半枚舉（bfs） + 雙指針

class Solution {
private:
    static const int MX = 40;
    static const int MXSIZE = (1<<20);
    int A[MXSIZE], B[MXSIZE]; // 將數組切成左右兩邊，存放各自產生出的序列，對應的數字總和
    void build(vector<int>& nums, int n, int OFFSET, int part[]) {
        // bfs
        int size = 0;
        part[size++] = 0; // 什麼都不選
        for(int i = 0; i < n; i++) { // 當前要選擇的
            int curSize = size;
            for(int j = 0; j < curSize; j++) {
                part[size++] = part[j] + nums[i + OFFSET];       
            }
        }
    }
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        build(nums, n / 2, 0, A);
        build(nums, n - n / 2, n / 2, B);

        sort(A, A + (1 << n / 2));
        sort(B, B + (1 << (n - n / 2)));
        
        // 合併左右，雙指針
        int res = INT_MAX;
        for(int left = 0, right = (1 << (n - n / 2)) - 1; left < (1 << n / 2); left++) {
            while(right >= 0 && A[left] + B[right] >= goal) {
                res = min(res, A[left] + B[right] - goal);
                right--;
            }
        }
        for(int left = 0, right = (1 << (n - n / 2)) - 1; right >= 0; right--) {
            while(left < (1 << n / 2) && A[left] + B[right] <= goal) {
                res = min(res, goal - A[left] - B[right]);
                left++;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\times 2^{n/2})$
• 空間複雜度：$O(n\times 2^{n/2})$