leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS

骑猪看日落 2022-06-04 08:18 192阅读 0赞

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:  
Each of the array element will not exceed 100.  
The array size will not exceed 200.  
Example 1:

Input: \[1, 5, 11, 5\]

Output: true

Explanation: The array can be partitioned as \[1, 5, 5\] and \[11\].  
Example 2:

Input: \[1, 2, 3, 5\]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

这道题可以使用DFS来做，**但是会超时**，我想到了使用DP动态规划，但是忘记又该怎么做了，这道题又一次给了一个警醒，DP动态规划真的是很难得，不过本题还是很简单了的dp\[i\]表示和为i是否可以被满足

这道题给了我们一个数组，问我们这个数组能不能分成两个非空子集合，使得两个子集合的元素之和相同。那么我们想，原数组所有数字和一定是偶数，不然根本无法拆成两个和相同的子集合，那么我们只需要算出原数组的数字之和，然后除以2，就是我们的target，那么问题就转换为能不能找到一个非空子集合，使得其数字之和为target。开始我想的是遍历所有子集合，算和，但是这种方法无法通过OJ的大数据集合。于是乎，动态规划DP就是我们的不二之选。我们定义一个一维的dp数组，其中dp\[i\]表示数字i是否是原数组的任意个子集合之和，那么我们我们最后只需要返回dp\[target\]就行了。我们初始化dp\[0\]为true，由于题目中限制了所有数字为正数，那么我们就不用担心会出现和为0或者负数的情况。那么关键问题就是要找出递归公式了，我们需要遍历原数组中的数字，对于遍历到的每个数字nums\[i\]，我们需要更新我们的dp数组，要更新\[nums\[i\], target\]之间的值，那么对于这个区间中的任意一个数字j，如果dp\[j - nums\[i\]\]为true的话，那么dp\[j\]就一定为true，于是地推公式如下：

dp\[j\] = dp\[j\] || dp\[j - nums\[i\]\] (nums\[i\] <= j <= target)

本题建议和[leetcode 698. Partition to K Equal Sum Subsets K个子集 + 深度优先搜索DFS][leetcode 698. Partition to K Equal Sum Subsets K_ _ _DFS] 一起学习

建议和这一道题[leetcode 518. Coin Change 2 动态规划DP][leetcode 518. Coin Change 2 _DP] 、[leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决][leetcode 279. Perfect Squares _ _ _DP] 、[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]一起学习

还有[leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题][leetcode 474. Ones and Zeroes_0_1_DP]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        bool canPartition(vector<int>& nums)
        {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum % 2 != 0)
                return false;
            int target = sum / 2;
            vector<bool> dp(target + 1, false);
            dp[0] = true;
            for (int num : nums)
            {
                for (int i = target; i >= num; i--)
                {
                    dp[i] = dp[i] || dp[i - num];
                }
            }
            return dp[target];
        }
    
        bool canPartitionBYDFS(vector<int>& a)
        {
            int sum = accumulate(a.begin(), a.end(), 0);
            if (sum % 2 != 0)
                return false;
            vector<bool> visit(a.size(), false);
            return dfs(a, visit, sum / 2, 0,0);
        }
    
        bool dfs(vector<int>& a, vector<bool>& visit,int tar,int sum,int start)
        {
            if (sum > tar)
                return false;
            else if (sum == tar)
                return true;
            else
            {
                for (int i = start; i < a.size(); i++)
                {
                    if (visit[i] == false)
                    {
                        visit[i] = true;
                        if (dfs(a, visit, tar, sum + a[i],i+1))
                            return true;
                        visit[i] = false;
                    }
                }
                return false;
            }
        }
    };

[leetcode 698. Partition to K Equal Sum Subsets K_ _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78883582
[leetcode 518. Coin Change 2 _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 279. Perfect Squares _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78117843
[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 474. Ones and Zeroes_0_1_DP]: http://blog.csdn.net/JackZhang_123/article/details/78781584