leetcode：1755. Sum of subsequences closest to the target value

Title source

• leetcode：1755. The sum of subsequences closest to the target value

Title Description

class Solution {
    
public:
    int minAbsDifference(vector<int>& nums, int goal) {
    

    }
};

title

Analyze the amount of data

Before looking at the question , Let's first look at the amount of data given ：$1<=nums.length<=40$, It means ：

• One side , It is almost impossible to have $O(N^2)、O(N^{2}logN)、O(N^3)$, Such time complexity , because [1,40] The data range of is too small
• On the other hand , It can't have $O(2^N)、O(N\ast 2^N)、O(3^N)$ Such time complexity , because [1,40] The data range of is too large

In general , Data volume $n<=20$, This implies that we should use a Exponential level algorithm To solve , For example, divide and conquer 、 to flash back 、dfs etc. , Like what dynamic planning and so on pass. So for $n<=40$, The only possibility is to 40 Split into two 20, Then run an exponential complexity solution on both sides

Then look at the data range , It seems a little big , Dynamic programming pass

Analyze the meaning of the question

Then come to the question . The title requires us to select some subsets from the array , the sum( A subset of ) Recently, I received goal.

Because the requirements are the closest , So we definitely need to look at all subsets .

Enumerating all subsets can be done by backtracking .

But because of the amount of data $n<=40$, If you enumerate all subsets, the complexity is $2^{4}0$, It's bound to time out , So we need to deal with it

Add

ps： About “ The sum of subsequences closest to the target value ” This kind of question ：

• If the array length is particularly large , But the value is small , We can solve the knapsack problem
• But if the array length is not big , But if the value is particularly large , Use DFS.

dfs

class Solution {
    
    int point = 0; //  Pointer to array data combination （ Indicates the subscript of an array ）
    /** * @param nums  The array given by the title  * @param start  The starting position of the array  * @param end  The end position of the array  * @param sum  Save the left combined sum （sum） * @param arr  Save the sum of the array combination  */
    void dfs(vector<int>& nums, int goal, int start, int sum, vector<int>& arr){
    
        arr[point++] = sum;
        for (int i = start; i < nums.size(); ++i) {
    
            dfs(nums, goal, i + 1, sum + nums[i], arr);
        }
    }
public:
    int minAbsDifference(vector<int>& nums, int goal) {
    
        int N = nums.size();
        int mid = N >> 1;
        point = 0;
        //  data { 5, -7, 3, 5 }==> left [5,-7]  On the right side [5,-2]
        //  Save the combination of all data on the left ==>[0, -7, 5, -2]  The data on the left is (5,-7)
        std::vector<int> l(1 << 20);
        //  Save the combination of all data on the right ==>[0, 5, 3, 8]  The data on the right is (5,-2)
        std::vector<int> r(1 << 20);


        dfs(nums, 0, mid - 1, 0, l); //  Enumerate all combinations on the left 
        point = 0;//  Pointer return 0
        dfs(nums, mid, N - 1, 0, r);//  Enumerate all combinations on the right 

        int ans = INT32_MAX;
        std::sort(l.begin(), l.end());
        std::sort(r.begin(), r.end());

        // Combine left data with right data 
        int left = 0, right = N - 1;
        for(int x : l){
    
            ans = std::min(ans, std::abs(goal - x));
        }
        for(int x : r){
    
            ans = std::min(ans, std::abs(goal - x));
        }
        while (left < N && right >= 0){
    
            int t = l[left] + r[right]; // Temporarily save the combination of left data and right data 
            ans = std::min(ans, std::abs(t - goal));
            if(t > goal){
    
                right--;
            }else{
    
                left++;
            }
        }

        return ans;
    }
};

violence （ Overtime ）

Enumerate all subsequences

class Solution {
    
    int ans = INT32_MAX;

    void dfs(vector<int>& nums, int goal, int start, int sum){
    
        ans = std::min(ans, std::abs(sum - goal));
        for (int i = start; i < nums.size(); ++i) {
    
            dfs(nums, goal, i + 1, sum + nums[i]);  // Notice that this is i+1...... It's easy to get wrong 
        }
    }
public:
    int minAbsDifference(vector<int>& nums, int goal) {
    
        if(nums.empty()){
    
            return goal;
        }

        dfs(nums, goal, 0, 0);
        return ans;
    }
};

Summary ： Data range n :

• n <= 20, Can be violent ,2^20
• n <= 40, No direct violence , But it can be half ,20 * 2^20