Commit 1d9e5cb

I have tried my best to write the most concise and efficient code, so I call it my best practice. If you have better solutions, welcome to create an issue or PR!

- [416. Partition Equal Subset Sum](problems/0416-partition-equal-subset-sum.md)

LeetCode problem: [416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)

* 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 `01 knapsack problem`. `01 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 `01 knapsack problem` uses a two-dimensional `dp` array or a one-dimensional `dp` **rolling array**, first **traverses the items**, then **traverses the knapsack in reverse**, 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 loop.

* 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`.

* The value of `dp[j]` is a boolean.

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

* Use an example:

```

```

* You can see the `dp` array size is one greater than the knapsack size. In this way, the backpack size and index value are equal, which helps to understand.

* `dp[0]` is set to `true`, indicating that an empty backpack can be achieved by not putting any items in it. In addition, it is used as the starting value, and the subsequent `dp[j]` will depend on it. If it is `false`, all values of `dp[j]` will be `false`.

* `dp[j] = false (j != 0)`, indicating that it is impossible to get `j` with no `nums`.

3. Determine the `dp` array's recurrence formula

* Try to complete the grid. In the process, you will get inspiration to derive the formula.

```

```

```

```

```

```

```

```

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

```python

dp[j] = dp[j] or dp[j - nums[i]]

```

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

* `dp[j]` depends on `dp[j]` and `dp[j - nums[i]]`, so we should traverse the `dp` array from top to bottom, then **from right to left**.

* Please think if we can traverse the `dp` array from top to bottom, then `from left to right`? In the `Python` code comments, I will answer this question.

5. Check the `dp` array's value

* Print the `dp` to see if it is as expected.

* Time: `O(n * sum/2)`.

* Space: `O(sum/2)`.

class Solution:

def canPartition(self, nums: List[int]) -> bool:

sum_ = sum(nums)

if sum_ % 2 == 1:

return False

dp = [False] * ((sum_ // 2) + 1)

dp[0] = True

for num in nums:

for j in range(len(dp) - 1, 0, -1): # If traverse from left to right, the newly assigned value `dp[j - num]` will affect the subsequent `dp[j]`. This is wrong because each `num` can only be used once.

if j < num:

break

dp[j] = dp[j] or dp[j - num]

return dp[-1]

class Solution {

public:

bool canPartition(vector<int>& nums) {

auto sum = reduce(nums.begin(), nums.end());

if (sum % 2 == 1)

return false;

auto dp = vector<bool>(sum / 2 + 1);

dp[0] = true;

for (auto num : nums)

for (auto j = dp.size() - 1; j >= num; j--)

dp[j] = dp[j] || dp[j - num];

return dp[dp.size() - 1];

}

};

class Solution {

public boolean canPartition(int[] nums) {

var sum = IntStream.of(nums).sum();

if (sum % 2 == 1)

return false;

var dp = new boolean[sum / 2 + 1];

dp[0] = true;

for (var num : nums)

for (var j = dp.length - 1; j >= num; j--)

dp[j] = dp[j] || dp[j - num];

return dp[dp.length - 1];

}

}

public class Solution {

public bool CanPartition(int[] nums) {

var sum = nums.Sum();

if (sum % 2 == 1)

return false;

var dp = new bool[sum / 2 + 1];

dp[0] = true;

foreach (var num in nums)

for (var j = dp.Length - 1; j >= num; j--)

dp[j] = dp[j] || dp[j - num];

return dp[dp.Length - 1];

}

}

var canPartition = function(nums) {

sum = _.sum(nums)

if (sum % 2 == 1)

return false

dp = Array(sum / 2 + 1).fill(false)

dp[0] = true

for (num of nums)

for (let j = dp.length - 1; j >= num; j--)

dp[j] = dp[j] || dp[j - num]

return dp.at(-1)

};

func canPartition(nums []int) bool {

sum := 0

for _, num := range nums {

sum += num

}

if sum % 2 == 1 {

return false

}

dp := make([]bool, sum / 2 + 1)

dp[0] = true

for _, num := range nums {

for j := len(dp) - 1; j >= num; j-- {

dp[j] = dp[j] || dp[j - num]

}

}

return dp[len(dp) - 1]

}

def can_partition(nums)

sum = nums.sum

return false if sum % 2 == 1

dp = Array.new(sum / 2 + 1, false)

dp[0] = true

nums.each do |num|

(1..(dp.size - 1)).reverse_each do |j|

break if j < num

dp[j] = dp[j] || dp[j - num]

end

end

return dp[-1]