- When we first see this problem, we might want to loop through all subsets of the array. If there is a subset whose sum is equal to`half of the sum`, then return`true`. This can be achieved with a`backtracking algorithm`, but after seeing the constraint`nums.length <= 200`, we can estimate that the program will time out.

- This is actually a`0/1 Knapsack Problem` which belongs to`Dynamic Programming`.`Dynamic programming` means that the answer to the current problem can be derived from the previous similar problem. Therefore, the`dp` array is used to record all the answers.

- The core logic of the`0/1 Knapsack Problem` uses a two-dimensional`dp` array or a one-dimensional`dp`**rolling array**, first**iterate through the items**, then**iterate through the knapsack size** (`in reverse order` or use`dp.clone`), then**reference the previous value corresponding to the size of current 'item'**.

- There are many things to remember when using a two-dimensional`dp` array, and it is difficult to write it right at once during an interview, so I won't describe it here.

- This problem can be solved using the`0/1 knapsack problem` algorithm.

These five steps are a pattern for solving`Dynamic Programming` problems.

1. Determine the**meaning** of the`dp[j]`

- We can use a one-dimensional`dp`**rolling array**. Rolling an array means that the values of the array are overwritten each time through the iteration.

- At first, try to use the problem's`return` value as the value of`dp[j]` to determine the meaning of`dp[j]`. If it doesn't work, try another way.

- So,`dp[j]` represents whether it is possible to`sum` the first`i``nums` to get`j`.

-`dp[j]` represents whether it is possible to`sum` the first`i``nums` to get`j`.

-`dp[j]` is a boolean.

2. Determine the`dp` array's initial value

- Use an example:

These five steps are a pattern for solving`Dynamic Programming` problems.

1. Determine the**meaning** of the`dp[j]`

- Since we are only considering the zero count constraint for now, we can use a one-dimensional`dp` array.

-`items` is`strs`,`backpack` is`max_zero_count`.

-`dp[j]` represents the maximum number of strings that can be selected with at most`j` zeros.

-`dp[j]` is an integer.

max_zero_count= m

dp= [0]* (max_zero_count+1)

```

- The`dp` array sizeis one greater than the zero count constraint. This way, the index value equals the constraint value, making it easier to understand.

-`dp[0] =0`, indicating thatwith no zeros, we can select0 strings.

-`dp[j] =0`as the initial value because we will use`max` to increase them later.

3.Determinethe`dp`array's recurrence formula

3.According to an example, fillinthe`dp`grid data"in order".

- Let's analyze the example step by step:

```

```

- After analyzing the sample`dp` grid, we can derive the`Recurrence Formula`:

dp[j]=max(dp[j], dp[j- zero_count]+1)

```

- This formula means:for each string, we can either:

1. Not select it (keep the current value`dp[j]`)

2. Select it (add1 to the value at`dp[j- zero_count]`)

4. According to the`dp` grid data, derive the"recursive formula".

4. Determine the`dp` array's traversal order

- First**iterate through the strings**, then**iterate through the zero count** (`in reverse order`).

- When iterating through the zero count, since`dp[j]` depends on`dp[j]`and`dp[j- zero_count]`, we should traverse**from right to left**.

- This ensures that we don't use the same string multiple times.

5. Check the`dp` array's value

- Print the`dp` to seeif itisas expected.

- The final answer will be at`dp[max_zero_count]`.

6. The code that only considers the quantity limit of`0`is:

dp[j]=max(dp[j], dp[j- zero_count]+1)

```

5. Write a programandprint the`dp` array. If itisnotas expected, adjust it.

- The code that only considers the quantity limit of`0`is:

classSolution:

return zero_count

```

It should be handled similarly to`0` butin another dimension. Please see the complete code below.

This problem is quite difficult if you have not solved similar problems before. So before you start working on this question, it is recommended that you first work on another relatively simple question[416. Partition Equal Subset Sum](416-partition-equal-subset-sum.md) that is similar to this one.

- When we see a set of numbers being used once to obtain another number through some calculation (just like this question), we can consider this to be a`0/1 Knapsack Problem`.

-`0/1 Knapsack Problem` belongs to`Dynamic Programming`.`Dynamic programming` means that the answer to the current problem can be derived from the previous similar problem. Therefore, the`dp` array is used to record all the answers.

- The core logic of the`0/1 Knapsack Problem` uses a two-dimensional`dp` array or a one-dimensional`dp`**rolling array**, first**traverses the items**, then**traverses the knapsack size** ([in reverse order](416-partition-equal-subset-sum.md) or use`dp.clone`), then**reference the previous value corresponding to the size of current 'item'**.

- There are many things to remember when using a two-dimensional`dp` array, and it is difficult to write it right at once during an interview, so I won't describe it here.

These five steps are a pattern for solving`Dynamic Programming` problems.

1. Determine the**meaning** of the`dp[j]`

- We can use a one-dimensional`dp`**rolling array**. Rolling an array means that the values of the array are overwritten each time through the iteration.

- At first, try to use the problem's`return` value as the value of`dp[j]` to determine the meaning of`dp[j]`. If it doesn't work, try another way.

- So,`dp[j]` represents that by using the**first**`i` nums, the**number** of different**expressions** that you can build, which evaluates to`j`.

-`dp[j]` represents that by using the**first**`i` nums, the**number** of different**expressions** that you can build, which evaluates to`j`.

-`dp[j]` is an**integer**.

2. Determine the`dp` array's initial value

- Use an example. We didn't use the`Example 1: Input: nums = [1,1,1,1,1], target = 3` because it is too special and is not a good example for deriving a formula.

- I made up an example:`nums = [1,2,1,2], target = 4`. The example must be simple, otherwise it would take too long to complete the grid.

- I made up an example:`nums = [1,2,1,2], target = 4`.

- First, determine the`size` of the knapsack.

- The`target` value may be very small, such as`0`, so it alone cannot determine the`size` of the knapsack.

- The sum of`nums` should also be taken into account to fully cover all knapsack sizes.