416. Partition Equal Subset Sum - Medium

前往題目

之前的文章

這次看到一樣想不出來，連code都花了一點時間才懂

思路

1. 先知道總和，就可以知道有沒有辦法被分成兩個subset了(因為要能被2整除才能分配成兩個subsets)
2. 目標target直接sum / 2，因為兩個subset總和相等
3. 疊代nums所有的element
4. 每個疊代中都使用新的一個hashset來儲存可能的數值(不然會導致還沒疊代完，dp就會被更新，這樣會更改到同一輪的數字)
5. 每個疊代中再疊代dp所有的element，每次都再加上當前的數字，有看到目標數字馬上回傳true，並記得附上原本dp中的element，因為要把疊代完後要把新的hashset賦給dp

Code

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;

        // Obtain sum
        for (int num : nums) sum += num;

        // Check if possible to half
        if (sum % 2 != 0) return false;

        Set<Integer> dp = new HashSet<>();
        dp.add(0); // At least 0

        // Get the target
        int target = sum / 2;

        // Iterate all the num in nums
        // 從前往後，從後往前都可以
        for (int i = nums.length - 1; i >= 0; --i) {
            // For preventing changing "dp" while iterating
            Set<Integer> nextDP = new HashSet<>();
            for (int t : dp) {
                // Return immed. when found the sol.
                if ((t + nums[i]) == target) return true;
                nextDP.add(t + nums[i]); // Add possible value
                nextDP.add(t); // Add origin
            }
            // Reassign the dp
            dp = nextDP;
        }
        return false;
    }
}

2024/06/30

• 只知道如何判斷是否可以partition😂