leetcode：494. All methods of adding and subtracting operators to the array to get the specified value

Title source

• leetcode：494. All methods of adding and subtracting operators to the array to get the specified value

Title Description

title

Recurrence of violence

Definition ： For arrays arr[idx…] All the numbers in , Come up with rest The number of , What is the method .

int process(std::vector<int>&arr, int idx, int rest);

base case：

• When there is no number , There is no choice , At this time rest Is it 0, If 0, A method has been found , There is no other way

In general ：

• Namely base case Other than that , That is, there are still numbers to choose from
• This is the time , We have to decide on arr[idx] Make a choice , Making a choice will be right rest Impact . Finally, the rest of the recursion is given to arr[idx+1…]

Memorandum

about ：

int process(std::vector<int>&arr, int idx, int rest);

As long as the variable parameters idx and rest Fixed , that process The return value of is fixed

therefore , We just use one map Refers to caching , And then if there is , Just check it out , If not, calculate

Violent recursion to dynamic programming

Optimize

The original problem is equivalent to ： find nums A positive subset P And a negative subset N, Make the sum equal to target. namely
$$sum(P)-sum(N)==target$$

At the same time there is ：

$$sum(P)+sum(N)==sum$$

Add the above two expressions , obtain
$$2\ast sum(P)==target+sum(nums)$$

among target + sum(nums) must >=0 And it is even , Otherwise, the equation cannot hold .

Then the question turns to ： There are some items , The first i The weight of each item is nums[i], The capacity of the backpack is sum§, ask ： How many ways to pack a backpack 【 Just full 】