[LeetCode] Partition Equal Subset Sum

Partition Equal Subset Sum

1.先除以2

2.每個DP位置每次都往前j-nums[i]看該位置有沒有更新

換句話說就是從dp[0]開始出發，

第一次先更新     0                    nums[0]

第二次更新0 + nums[1],  nums[0] + nums[1]

樹狀圖展開(Backtracking or DFS)

最後檢查dp[sum/2]這個位置有沒有訪問過

Loop 寫法

bool canPartition(vector<int>& nums) {
    int sum = 0;
    
    for(int i = 0; i < nums.size(); i++)
        sum += nums[i];
    if(sum%2)
        return false;
    
    vector<int> dp(sum/2+1,0);
    dp[0] = 1;

    for (int i = 0; i < nums.size(); i++) {
        for (int j = sum/2; j >= nums[i]; j--)
            dp[j] = dp[j] || dp[j-nums[i]];
    }
    
    return dp[sum/2];
}

Recursion: 會TLE XD

vector<int> dp;
vector<int> nums;

bool canPartition(vector<int>& nums) {
    int sum = 0;
    
    for(int i = 0; i < nums.size(); i++)
        sum += nums[i];
    if(sum%2)
        return false;
    
    dp.resize(sum/2+1,0);
    this->nums = nums;
    
    dfs(0, 0);
    
    return dp[sum/2];
}

void dfs(int cur, int index) {
                  
    
    if(index + 1 < nums.size()) {
        dfs(cur, index + 1);
        dfs(cur + nums[index], index + 1);
    }
    
    if(cur < dp.size()) {
        if(dp[cur] == 1)
            return;
        else
            dp[cur] = 1;
    }
}