【Day 61 】2021-11-09 - 416. 分割等和子集

[azl397985856]

416. 分割等和子集

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/partition-equal-subset-sum/

前置知识

暂无

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

[yanglr]

思路:

题意: 原数组中可能会有重复的数。

原数组如果能分成和相等的两组, 那么需要满足数组中元素的总和是2的倍数。

方法1: 回溯

dfs(回溯)可以做, 但会超时TLE, 故只能用dp做了。

方法2: 动态规划

类似于0、1背包问题, 每一个元素都有选或不选两种状态。

将原数组中的元素总和记作sum, 要求的 targetSum=sum/2。

根据题目给的数据范围:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

可知, sum所属的范围是[0, 20000]。 那么如果dp数组中dp[i]里i的范围是0~sum, 那么dp数组的长度接近于20000。

这个数据范围dp的表现应该会挺不错的。

dp数组

dp[i]: 原数组nums的子序列的和能达到i 就记作 true, 否则记为false。

对于原数组nums中的任意一个元素num, 都有选或不选两种状态。 故 dp[i] = dp[i] || dp[i-num] (其中 i >= num) 选num 或 不选num

代码:

实现语言: C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum0 = accumulate(nums.begin(), nums.end(), 0);
        if (sum0 % 2 != 0) return false; // 总和是偶数才有可能分成两组       
        int sum = sum0 / 2;
        bool dp[sum + 1]; // dp[i]: 数组nums是子序列的和是否能达到i, 能就记作true, 否则false。 每新来一个数nums[i], 都有选或不选两种状态
        fill(dp, dp + sum + 1, false);
        dp[0] = true;
        for (auto& num : nums)
        {
            for (int j = sum; j >= 0; j--)
            {
                if (j >= num)
                    dp[j] = dp[j] || dp[j - num];
            }            
        }
        return dp[sum];
    }
};

复杂度分析

• 时间复杂度: O(M*N), 其中 M是数组nums的最大值, N是数组nums的长度
• 空间复杂度: O(M*N)

[ysy0707]

思路：动态规划

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        //等和子集的和必是总和的一半, 如果总和是奇数，直接返回false
        int sum = 0;
        for(int i: nums){
            sum += i;
        }
        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean [n][target + 1];
        // 先填表格第 1 行，第 1 个数只能让容积为它自己的背包恰好装满
        dp[0][0] = true;
        if(nums[0] <= target){
            dp[0][nums[0]] = true;
        }
        //开始填表[1,len - 1]
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= target; j++){
                if(j >= nums[i]){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
            //判断是否需要提前结束计算
            if (dp[i][target]) return true;
        }
        return dp[n - 1][target];
    }
}

时间复杂度: O(M N) 空间复杂度: O(M N)

[leo173701]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        def dfs(nums, target, cache):
            if target < 0: return False
            if target == 0: return True
            if target in cache: return False
            cache.add(target)
            for i, n in enumerate(nums):
                if dfs(nums[i+1:], target-n, cache): return True
            return False

        s = sum(nums)
        if s % 2 != 0: 
            return False
        return dfs(nums, s//2, set())

[biancaone]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if not nums:
            return False

        sums = sum(nums)

        if sums % 2 != 0:
            return False

        return self.memo_search(nums, 0, 0, sums // 2, {})

    def memo_search(self, nums, index, cur_sum, target, memo):
        if (index, cur_sum) in memo:
            return memo[(index, cur_sum)]

        if index == len(nums) or cur_sum > target:
            return False

        if cur_sum == target:
            return True

        result = self.memo_search(nums, index + 1, cur_sum, target, memo) or self.memo_search(nums, index + 1, cur_sum + nums[index], target, memo)

        memo[(index, cur_sum)] = result

        return result

[ZacheryCao]

Idea:

DP: dp[i][j] whether we can use a subset in nums[0]~nums[i] to form a sum j.

Code:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False
        target = total//2
        dp = [[False for _ in range(target + 1)] for _ in range(len(nums)+1)]
        dp[0][0] = True
        for i in range(1, len(nums) + 1):
            cur = nums[i - 1]
            for j in range(target + 1):
                dp[i][j] = dp[i-1][j] if j < cur else (dp[i-1][j] or dp[i-1][j - cur])
        return dp[-1][-1]

Complexity:

Time: O(M N) M: half of totalsum. N: length of nums Space: O(M N)

[JiangyanLiNEU]

Idea

• memorization

• Runtime = O(mn)

  JavaScript

  var canPartition = function(nums) {
  let summ = 0;
  for (let num of nums){
      summ += num;
  };
  
  if (summ%2 != 0){
      return false;
  }else{
      const target = summ/2;
      let memo = new Map();
      let aSet = new Set();
      if (nums[nums.length-1] ==  target){
          return true;
      }
      aSet.add(nums[nums.length-1]);
      memo.set(nums.length-1, aSet);
      for (let i=nums.length-2; i>=0; i--){
          const num = nums[i];
          let value = new Set();
          for (let item of memo.get(i+1)){
              if (item == target || item+num == target){
                  return true;
              };
              value.add(item);
              value.add(item+num);
          };
          memo.set(i, value);
      };
      return false;
  }
  };

[wangzehan123]

Java Code:

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}

[florenzliu]

Explanation

• equal to find a subset with sum of sum(nums) // 2
• top down approach using dfs + memoization
• bottom up approach using 2-D dp[i][j]: true if the sum j can be formed by array elements in the subset nums[0] ~ nums[i]
  • dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
• improve space complexity using 1-D dp[i]: true if the sum i can be formed
  • dp[i] = dp[i] or dp[i-currNum]

Python

class Solution:
    # Approach 1: top down dynamic programming
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        target = sum(nums) // 2
        @lru_cache(maxsize=None)
        def dfs(n, currSum):
            if currSum < 0 or n < 0:
                return False
            if currSum == 0:
                return True
            return dfs(n-1, currSum) or dfs(n-1, currSum-nums[n])
        return dfs(len(nums)-1, target)

    # Approach 2: bottom up dynamic programming
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        target = sum(nums) // 2
        dp = [[0 for _ in range(target+1)] for _ in range(len(nums)+1)]
        dp[0][0] = 1

        for i in range(1, len(nums)+1):
            for j in range(target+1):
                if j < nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
        return dp[-1][target]

    # Approach 3: 1d dynamic programming
        if sum(nums) % 2:
            return False
        target = sum(nums) // 2
        dp = [0 for _ in range(target+1)]
        dp[0] = 1
        for n in nums:
            for i in range(target, n-1, -1):
                dp[i] = dp[i] or dp[i-n]
        return dp[-1]        

Complexity:

• Time Complexity: O(mn) where m is the length of nums list and n is the subsetSum, i.e., total_sum / 2
• Space Complexity: O(mn) or O(n)

[pophy]

思路1

• DFS - TLE

思路2

• 动态规划 knapsack
• 数组求和 sum 如果sum是奇数直接false
• 题目转化为能否找到一个subset满足大小为sum/2的背包问题

Java Code

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j + nums[i] <= sum && dp[j]) {
                    dp[j + nums[i]] = true;
                }
            }
        }
        return dp[sum];
    }

时间&空间

• 时间 O(m*n) m数组大小 - n数组最大数
• 空间 O(m*n)

[littlemoon-zh]

转换问题： 如果sum(nums)是奇数，return false 否则，找到一个子数组，使得和是 sum(nums) / 2，所以是个背包问题。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target & 1: return False
        target = target // 2
        Vs = [False] * (target + 1)
        Vs[0] = True
        for i in range(len(nums)):
            for j in range(target, nums[i]-1, -1):
                Vs[j] = Vs[j - nums[i]] or Vs[j]
            if Vs[-1]:
                return True

        return False

[zhangzz2015]

思路

• 因为能分成两个子集同时元素和相等，可转化为等价问题，在数组中找到一个子集，子集的和为 totalSum/2。先考虑dfs + mem。定义 g 为num 数组，定义两维函数dp(x,y) 为在[0 y] 范围的数组里能否找到target 为x 的子集，该问题可转化为 [0, y-1] 中找到target=x 的子集，或者 [ 0 y-1] 中找到 target = x - num[y]，其中一个能找到则表明可以找到。函数关系为dp(x, y) = dp(x, y-1) || dp(x - num[y] , y-1)
• 方法1， 采用 top down 方法，dfs + mem。时间复杂度为O(n m )，空间复杂度为O(nm) n 为数组的num， m 为target
• 方法2， 也可采用dp 方法, 时间复杂度为O(n m )，空间复杂度为O(nm)
• 方法3， 因为当前dp状态之和上一次dp 相关，可压缩。采用倒序方法，时间复杂度为O(n*m)，空间复杂度为O(m)

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        // 
        int total =0; 
        for(int i=0; i< nums.size(); i++)
            total +=nums[i]; 
        if(total%2==1) // odd
            return false; 

        total = total/2; 

        /// find subset and target is equal to total. 
        // we build two diemention dp function. 
        //   g is nums.   y means you can choose [0 y] 
        //   x is target 
        //  dp(x, y) =  dp(x, y-1 ) || (dp(x-g[y], y-1)); 
        unordered_map<int, unordered_map<int,bool>> mem; 
        return dfs(nums, total, nums.size()-1, mem); 

    }

    bool dfs(vector<int>& nums, int target, int prevIndex, unordered_map<int, unordered_map<int, bool>>& mem)
    {
        if(target==0)
            return true; 
        if(target<0)
            return false;
        if(prevIndex<0)
            return false; 

        if(mem.find(target)!=mem.end() && mem[target].find(prevIndex) !=mem[target].end())
            return mem[target][prevIndex]; 
        bool find = false;
        find |= dfs(nums, target, prevIndex-1, mem); 
        if(find)
            return true; 
        find |= dfs(nums, target-nums[prevIndex], prevIndex-1, mem); 
        mem[target][prevIndex] = find;             
        return find; 
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        // 
        int total =0; 
        for(int i=0; i< nums.size(); i++)
            total +=nums[i]; 
        if(total%2==1) // odd
            return false; 

        total = total/2; 

        /// find subset and target is equal to total. 
        // we build two diemention dp function. 
        //   g is nums.   y means you can choose [0 y] 
        //   x is target 
        //  dp(x, y) =  dp(x, y-1 ) || (dp(x-g[y], y-1)); 

        vector<vector<bool>>  dpTable(nums.size()+1, vector<bool>(total+1, false)); 

        for(int i=0; i <=nums.size(); i++)        
        {
            for(int j=0; j<=total; j++)
            {
                if(j==0)
                 dpTable[i][j] =  true; 
                else if(i==0)
                 dpTable[i][j] = false;  
                else
                {
                  dpTable[i][j] =(dpTable[i][j] || dpTable[i-1][j]); 
                if(j>=nums[i-1])
                 dpTable[i][j] = (dpTable[i][j] || dpTable[i-1][j- nums[i-1]]);                 
                }
            }
        }

        return dpTable[nums.size()][total]; 
    }

};

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        // 
        int total =0; 
        for(int i=0; i< nums.size(); i++)
            total +=nums[i]; 
        if(total%2==1) // odd
            return false; 

        total = total/2; 

        /// find subset and target is equal to total. 
        // we build two diemention dp function. 
        //   g is nums.   y means you can choose [0 y] 
        //   x is target 
        //  dp(x, y) =  dp(x, y-1 ) || (dp(x-g[y], y-1)); 

        vector<bool>  dpTable(total+1, false); 

        for(int i=0; i <=nums.size(); i++)        
        {
            for(int j=total; j>=0; j--)
            {
                if(j==0)
                 dpTable[j] =  true; 
                else if(i==0)
                 dpTable[j] = false;  
                else
                {
                if(j>=nums[i-1])
                 dpTable[j] = (dpTable[j] || dpTable[j- nums[i-1]]);                 
                }
            }
        }

        return dpTable[total]; 
    }  
};

[skinnyh]

Note

• The problem is same as whether can find a subset which sum equals to total_sum / 2
• It is a backpack problem. dp[i][j] means whether the first i numbers can make the sum of j. dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]pick or not pick element i. And dp[0][0] = true The result is dp[n][total_sum / 2]
• Since dp[i][j] only relates to the last layer, we can use 1D array to compress space. Specially, we need to iterate j decreasingly to avoid overwriting current layer before calculation.

Solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        total = total // 2
        # dp[i][j] means whether the first i numbers can make the sum of j
        # dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]] pick or not pick i
        dp = [False] *  (total + 1)
        dp[0] = True
        for i in range(len(nums)):
            for j in range(total, 0, -1):
                if j >= nums[i]:
                    dp[j] |= dp[j - nums[i]]
        return dp[total]

Time complexity: O(N * M) M = total_sum / 2

Space complexity: O(M)

[yingliucreates]

link:

partition-equal-subset-sum/

代码 Javascript

const canPartition = function(nums) {
    if(!nums) return false
    let total = nums.reduce((a,b) => a + b, 0)

    if(total%2 != 0) return false

    let target = total /2
    let arr = new Array(target + 1).fill(false)
    arr[0] = true

    for(let el of nums) {

        for(let i = target; i >=0; i--) {            
            let complement = i - el

            if(!arr[i] && arr[complement]){
                arr[i] = true
            }
            if(arr[target] == true) return true
        }
    }

    return false
};

[shawncvv]

思路

动态规划

代码

JavaScript Code

var canPartition = function (nums) {
  let sum = nums.reduce((acc, num) => acc + num, 0);
  if (sum % 2) {
    return false;
  }
  sum = sum / 2;
  const dp = Array.from({ length: sum + 1 }).fill(false);
  dp[0] = true;

  for (let i = 0; i < nums.length; i++) {
    for (let j = sum; j > 0; j--) {
      dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);
    }
  }

  return dp[sum];
};

复杂度

• 时间复杂度：O(n∗m)
• 空间复杂度：O(n)

[yan0327]

思路： 从整体入手，对整个数组求和得到sum0，判断sum0/2是否为整数，不是整数则直接返回false 若是整数，再进一步讨论。生成一个dp数组 特性方程 dp[j] = dp[j] || dp[j - nums[i]] =>对于每种情况，可以考虑取或者不取的情况 我们以dp[0] = true作为初始条件 对数组nums进行遍历 ，取sum0的一半sum为每次入参 由于要充分考虑每一种可能，所以这里使用dfs，即对数组的每位遍历，都需要从sum遍历到0，考虑是否满足条件 =》剪枝：只有sum >= nums[i]才进行运算，否则为负值没有讨论价值 最后只要判断dp[sum] 是否为true，从而判断能否找到一组子集实现需求

func canPartition(nums []int) bool {
    sum0 := 0 
    for i:=0;i<len(nums);i++{
        sum0 += nums[i]
    }
    if sum0 %2 != 0{
        return false
    } //以上是为了判断是否存在二分的整数条件
    sum := sum0/2
    dp := make([]bool,sum+1)
    dp[0] = true //初始条件
    for i:=0;i<len(nums);i++{   //每个n次
        for j:= sum;j>=0;j--{   //每个m次（n/2）其实是属于DFS
            if j >= nums[i]{     //剪枝=》把负数情况摘掉
                dp[j] = dp[j] || dp[j-nums[i]]
            }
        }
    }
    return dp[sum]   //判断是否能组成这个值
}

时间复杂度O(m*n) 其中m为n/2 空间复杂度O（n）

[Daniel-Zheng]

思路

动态规划。

代码(C++)

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        int sum = 0, maxNum = 0;
        for (auto& num : nums) {
            sum += num;
            maxNum = max(maxNum, num);
        }
        if (sum & 1) return false;
        int target = sum / 2;
        if (maxNum > target) return false;
        vector<int> dp(target + 1, 0);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) dp[j] |= dp[j - num];
        }
        return dp[target];
    }
};

复杂度分析

• 时间复杂度：O(NM)
• 空间复杂度：O(M)

[okbug]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), m = 0;
        for (auto x: nums) m += x;
        if (m % 2) return false;
        m /= 2;
        vector<int> f(m + 1);
        f[0] = 1;
        for (auto x: nums) {
            for (int j = m; j >= x; j--) {
                f[j] |= f[j - x];
            }
        }

        return f[m];
    }
};

[Francis-xsc]

思路

动态规划 找到部分和为数组元素和的一半 转化为01背包问题

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int target=0;
        for(int x:nums){
            target+=x;
        }
        if(target%2)    return false;
        target/=2;
        vector<vector<int>>b(nums.size(),vector<int>(target+1,0));
        for(int i=1;i<nums.size();i++){
            for(int j=0;j<=target;j++){
                if(nums[i]<=j){
                    b[i][j]=max(b[i-1][j],b[i-1][j-nums[i]]+nums[i]);
                }
                else{
                    b[i][j]=b[i-1][j];
                }
            }
        }
        return b.back().back()==target;
    }
};

复杂度分析

• 时间复杂度：O(N*target)，其中 N 为数组长度。
• 空间复杂度：O(1)

[HondryTravis]

思路

动态规划

1. 要被分割成两个相同的子集，那肯定 sum%2 肯定不能够有剩余的
2. 之后就是 dp ，背包思路了

   代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const n = nums.length;
  if (n < 2) {
    return false;
  }
  // 分割成相近的两个子集，那必须要和无线接近
  const sum = nums.reduce((acc, cur) => acc + cur, 0)

  // 如果是奇数就不满足条件
  if (sum % 2 === 1) return false

  const target = Math.floor(sum / 2)
  // 二维 dp
  // j 表示最大容量为 target 的一半
  // i 表示每个数字，也就是每个物品
  const dp = new Array(n).fill(0).map(v => new Array(target + 1, false));

  // 初始化第一列的值
  for (let i = 0; i < n; i++) {
    dp[i][0] = true;
  }
  // 初始化 dp[0][nums[0]]
  dp[0][nums[0]] = true;

  // 开始遍历
  for (let i = 1; i < n; i++) {
    const num = nums[i];
    for (let j = 1; j <= target; j++) {
      // 如果当容量大于 j nums[i] 时
      if (j >= num) {
        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n - 1][target]
};

复杂度分析

时间复杂度 O(target*n)

空间复杂度 O(n)

[liuyangqiQAQ]

传统的dp

class Solution {
    public boolean canPartition(int[] nums) {
        //如果他们两个子集能够相等他们的总和必定为偶数
        int sum = Arrays.stream(nums).sum();
        //如果是奇数直接返回false
        if((sum & 1) == 1) return false;
        //定义当前背包最大能接受价格
        int n = sum / 2;
        int[][] dp = new int[nums.length + 1][n + 1];
        //利用背包问题求解看是否能求得m个商品的价钱正好达到n。如果达到则返回true，否则false
        //背包容量=背包价值求解
        for (int i = 1; i < nums.length + 1; i++) {
            int num = nums[i - 1];
            for (int j = 1; j < n + 1; j++) {
                if(j >= num) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - num] + num);
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][n] == n;
    }
}

时间复杂度: O(N)(sum(nums)) N为数组长度 sum(nums)为数组之和

空间复杂度: O(N)(sum(nums)) N为数组长度 sum(nums)为数组之和

有一维数组代替前一项数据

class Solution {
    public boolean canPartition(int[] nums) {
        //如果他们两个子集能够相等他们的总和必定为偶数
        int sum = Arrays.stream(nums).sum();
        //如果是奇数直接返回false
        if((sum & 1) == 1) return false;
        //定义当前背包最大能接受价格
        int n = sum / 2;
        //由于题意的状态转移只和前一状态相关。我们用一个一维数据维护即可
        int[] dp = new int[n + 1];
        //利用背包问题求解看是否能求得m个商品的价钱正好达到n。如果达到则返回true，否则false
        for (int i = 1; i < nums.length + 1; i++) {
            int num = nums[i - 1];
            int[] curDp = new int[n + 1];
            for (int j = 1; j < n + 1; j++) {
                if(j >= num) {
                    curDp[j] = Math.max(dp[j], dp[j - num] + num);
                }else {
                    curDp[j] = dp[j];
                }
            }
            dp = curDp;
        }
        return dp[n] == n;
    }
}

时间复杂度: O(N)(sum(nums)) N为数组长度 sum(nums)为数组之和

空间复杂度: O(sum(nums))

[joeytor]

思路

使用动态规划, 0/1 背包的思路

需要找出一个子集, sum 为 sum(nums)/2, 每个元素可选可不选并且只能最多使用一次

dp[i][j] 只使用前 i 个元素的情况下, 能否有子集的和等于 j

base case dp[i][0] = 0 for all i, dp[0][nums[0]] = 1 if nums[0] ≤ target

动态转移

dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]] if j-nums[i] ≥ 0

dp[i][j] = dp[i-1][j] if j-nums[i] < 0

如果 j - nums[i] ≥ 0, 并且 dp[i-1][j-nums[i]] = True, 那么代表可以使用前 i-1 个数字构成 j-nums[i], 再加上这一轮的 nums[i] 可以构成 数字 j, 所以 dp[i][j] = True

否则 dp[i][j] = dp[i-1][j] 代表看前 i-1 个数字能否构成 数字 j

return dp[-1][int(s/2)] 返回 用所有数能否构成 target (sum/2)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        l = len(nums)

        if s % 2 != 0:
            return False

        dp = [[False for i in range(int(s/2)+1)] for _ in range(l)]
        for i in range(l):
            dp[i][0] = True

        if nums[0] <= int(s/2):
            dp[0][nums[0]] = True
        for i in range(1, l):
            for j in range(0, int(s/2)+1):
                if j-nums[i] >= 0:
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[l-1][int(s/2)]

复杂度

l 为 nums 的长度, target 为 sum/2

时间复杂度: O(l * target) 两层循环的时间复杂度

空间复杂度: O(l * target) dp 数组的空间复杂度

[shamworld]

var canPartition = function(nums) {
    let total = nums.reduce((a,b)=>a+b,0);
    const len = nums.length;
    if(total%2){
        return false;
    }
    total = total/2;
    let dp = Array.from({length:len}).fill(false);
    dp[0] = true;
    for(let i = 0; i < len; i++){
        for(let j = total; j > 0; j--){
            dp[j] = dp[j]||(j - nums[i] >= 0 && dp[j - nums[i]]);
        }
    }
    return dp[total];
};

[james20141606]

Day 61: 416. Partition Equal Subset Sum (DP, knapsack)

• Problem Link

  • 416. Partition Equal Subset Sum

• Ideas

  • a knapsack problem, the key is to convert it to knapsack. There are three special cases, especially maxNum > total // 2
  • then we could have a 2D DP, dp[i][j] means selecting from array[0,i] if it could sum up to j. dp[i][0] == True (we do not select any num), and dp[0][nums[0]] == True
  • then for the transition: if j >= nums[i], we could select nums[i] or not, if one of the two options is true, it is true. If not select: dp[i][j]=dp[i−1][j], if select: dp[i][j]=dp[i−1][j−nums[i]]. if j < nums[i], we could not select nums[i]! dp[i][j]=dp[i−1][j]. Note for j we should loop through 1 to target
  • and we could also simplify 2D dp to 1D. loop j in reversed order from target to num - 1

• Complexity: hash table and bucket

  • Time: O(length * target)
  • Space: O(target)

• Code

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False
        total = sum(nums)
        maxNum = max(nums)
        if total & 1:
            return False
        target = total // 2
        if maxNum > target:
            return False

        dp = [[False] * (target + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = True

        dp[0][nums[0]] = True
        for i in range(1, n):
            num = nums[i]
            for j in range(1, target + 1):
                if j >= num:
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[n - 1][target]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False

        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]

        return dp[target]

• other resources:

[kidexp]

thoughts

背包dp，利用sum的空间是O(half_sum), half_sum 是数组的和的一半

code

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 == 1:
            return False
        half_sum = total_sum // 2
        sum_set = {0}
        for i in range(len(nums)):
            for sum_ in list(sum_set):
                if sum_ + nums[i] == half_sum:
                    return True
                elif sum_ + nums[i] < half_sum:
                    sum_set.add(sum_ + nums[i])

        return False

complexity

half_sum 是数组的和的一半， n是数组的长度 Time O( half_sum*n)

Space O( half_sum)

[chakochako]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False

        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]

        return dp[target]

[ForLittleBeauty]

思路

---

把划分问题，转化为凑到一个target的问题，也就是背包问题。

用动态规划解。

状态转移方程为 dp[i][j]= dp[i-1][j] || dp[i-1][j-num[i]]，观察到更新只依赖前面的结果后，可以转化为一维数组。

---

代码

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

        if sum(nums)%2!=0:
            return False
        else:
            target = sum(nums)//2

        dp = [True if i==nums[0] else False for i in range(target+1)]
        dp[0] = True

        for i in range(1,len(nums)):
            for j in range(target,-1,-1):
                if j-nums[i]>=0:
                    if dp[j-nums[i]]:
                        dp[j] = True

        return dp[-1]

---

时间复杂度: O(m*n))

空间复杂度: O(n)

其中m为数组长度,n为sum的一半

[chun1hao]

var canPartition = function(nums) {
    let sum = nums.reduce((r,c)=> r+c) / 2
    if(Math.floor(sum) !== sum) return false
    let dp = Array.from({length: nums.length}, ()=>[])
    if(nums[0] < sum){
        dp[0][nums[0]] = true
    }
    for(let i=1;i<nums.length;i++){
        for(let j=0;j<=sum;j++){
            dp[i][j] = dp[i-1][j]
            if(nums[i] == j){
                dp[i][j] = true
                continue
            }
            if(nums[i]<j){
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
            }
        }
    }
    return dp[nums.length-1][sum] || false
};

[EggEggLiu]

思路

动态规划

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2) return false;
        int m = sum / 2;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(j >= nums[i - 1]) f[i][j] = f[i - 1][j - nums[i - 1]] | f[i - 1][j];
                else f[i][j] = f[i - 1][j];
            }
        }
        return f[n][m];
    }
};

复杂度

O(m * n)

[watermelonDrip]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums) 
        if target&1: return False

        target = target>>1
        dp = [ [ False for _ in range(target+1)] for _ in range(len(nums))]

        for i in range(len(nums)):
            for j in range(target+1):
                if j == nums[i]:
                    dp[i][j] = True 
                if j - nums[i] > 0:
                    dp[i][j] =  dp[i-1][j] or dp[i-1][j-nums[i]]
                if j - nums[i] < 0:
                    dp[i][j] = dp[i-1][j]

        return dp[-1][-1]

[KennethAlgol]

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0;i < nums.length;i++){
            sum = sum + nums[i];
        }
        if(sum%2 != 0){
            return false;
        }

        int n = nums.length;
        //能分成两份的数组
        int target = sum / 2;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean[n][target + 1];
        // 先填表格第 1 行，第 1 个数只能让容积为它自己的背包恰好装满
        dp[0][0] = true;
        if(nums[0] <= target){
            dp[0][nums[0]] = true;
        }
        //开始填表[1,len - 1]
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= target; j++){
                if(j >= nums[i]){
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
            //判断是否需要提前结束计算
            if (dp[i][target]) {
                return true;
            }
        }
        return dp[n - 1][target];

    }
}

[laofuWF]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 == 1:
            return False
        target = total_sum // 2
        n = len(nums)

        dp = [[False] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = True
        for i in range(1, n + 1):
            curr = nums[i - 1]
            for j in range(target + 1):
                if j < curr:
                    dp[i][j] = dp[i - 1][j]
                else:
                    if dp[i - 1][j] or dp[i - 1][j - curr]:
                        dp[i][j] = True
                    else:
                        dp[i][j] = False

        return dp[n][target]

[zhy3213]

思路

dp，这个题和其他dp问题有所变化，dp数组中的索引不再是索引，而变成了实在的数值，打破这个思维定式后，其实不难理解。

代码

    def canPartition(self, nums: List[int]) -> bool:
        if len(nums)<2:
            return False
        s=sum(nums)
        if s%2:
            return False
        target=s//2
        if target<max(nums):
            return False
        last=[False]* (target+1)
        last[nums[0]]=True
        for i in range(1,len(nums)):
            new=[False]*(target+1)
            for j in range(target+1):
                if last[j] or last[j-nums[i]]:
                    new[j]=True
            last=new
        return new[target]

[akxuan]

转换成 0-1 背包问题, target 就是 sum(List)/2 .

public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        boolean[][] dp = new boolean[len][target + 1];

        // 初始化成为 true 虽然不符合状态定义，但是从状态转移来说是完全可以的
        dp[0][0] = true;

        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (nums[i] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }

            // 由于状态转移方程的特殊性，提前结束，可以认为是剪枝操作
            if (dp[i][target]) {
                return true;
            }
        }
        return dp[len - 1][target];
    }
}

[RocJeMaintiendrai]

题目

https://leetcode-cn.com/problems/partition-equal-subset-sum/

思路

DP

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int num : nums) {
            total += num;
        }
        if(total %2 != 0) return false;

        return canPartition(nums, 0, 0, total, new HashMap<String, Boolean>());
    }

    private boolean canPartition(int[] nums, int index, int sum, int total, HashMap<String, Boolean> state) {
        String cur = index + "" + sum;
        if(state.containsKey(cur)) {
            return state.get(cur);
        }
        if(sum * 2 == total) {
            return true;
        }
        if(sum > total / 2 || index >= nums.length) {
            return false;
        }

        boolean foundPartition = canPartition(nums, index + 1, sum, total, state) || canPartition(nums, index + 1, sum + nums[index], total, state);
        state.put(cur, foundPartition);
        return foundPartition;
    }
}

复杂度分析

时间复杂度

O(m n)

空间复杂度

O(n)

[lilyzhaoyilu]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
      int n = nums.size();
      if(n < 2) return false;

      int sum = 0, maxN = 0;

      for(auto& num: nums){
        sum += num;
        maxN = max(maxN, num);
      }

      if(sum & 1) return false;

      int target = sum / 2;

      if(maxN > target) return false;

      vector<int> dp(target + 1, 0);

      dp[0] = true;

      for(int i = 0; i < n; i++){
        int num = nums[i];
        for(int j = target; j >= num; j--){
          // dp[j] = dp[j] | dp[j - num]
          dp[j] |= dp[j - num];
        }
      }

      return dp[target];
    }
};

[pan-qin]

Idea:

partition nums into two sets, with each set's sum equals half of the total sum. Similar to backpack problem, we need to decide whether or not to pick one element so that certain combination of picked elements can sum up to a target value. Use a boolean dp[][] array, dp[i][j] stores whether using nums[0]...nums[i] can give a sum of j. So answer is dp[n][target]. For nums[i], whether using/or not using it can give sum j actually depends on dp[i-1][j]. dp[i][j] is true if:1) dp[i-1][j] is true; 2) dp[i-1][j-nums[i]] is true. So dp[i][j]=dp[i-1][j]|| dp[i-1][j-nums[i]].

Complexity:

Time: O(ntarget) Space: O(ntarget)

class Solution {
    public boolean canPartition(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for(int n:nums)
            sum+=n;
        if(sum%2==1)
            return false;
        int target = sum/2;
        int n =nums.length;
        boolean[][] dp = new boolean[n+1][target + 1];
        //dp[i][j] store whether the using num[0]...num[i] can have target sum j
        //dp[i][j]=dp[i-1][j]|| dp[i-1][j-nums[i]]
        dp[0][0]=true;
        for(int i=1;i<=n;i++) {
            int t=nums[i-1];
            for(int j=0;j<=target;j++) {
                boolean no = dp[i-1][j];
                //check if pick nums[i-1] will exceed target
                boolean yes = j>=t? dp[i-1][j-t]:false;
                dp[i][j]= no || yes;
            }
        }

        return dp[n][target];
    }
}

[shixinlovey1314]

Title:416. Partition Equal Subset Sum

Question Reference LeetCode

Solution

First get the sum of the entire array, if sum is an odd number, the array won't be split into 2 parts. Then, build 2-d array dp, dp[i][j] to depict whether possible to get a sum of j by using a subarrar from [0,j]. dp[i][j] = dp[i-1][j] /not take i/ | dp[i][j-nums[i]] /take i/

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums)
            sum += num;

        if (sum % 2)
            return false;

        sum /= 2;

        // dp[i][j]: if it is possible to get a sum of j with subsets from [0,i].
        vector<vector<bool>> dp(nums.size(), vector<bool>(sum + 1, false));

        // It is possible for each postion to have sum of 0 - we just don't pick any number.
        for (int i = 0; i < nums.size(); i++) {
            dp[i][0] = true;

            if (i <= sum)
                dp[i][i] = true;
        }

        for (int i = 1; i < nums.size(); i++)
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i-1][j];

                if (j >= nums[i])
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]];
            }

        return dp[nums.size() - 1][sum];
    }
};

Complexity

Time Complexity and Explanation

O(n * w): w is the half of the sum

Space Complexity and Explanation

O(n * w)

[ai2095]

416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Topics

• DP

思路

It's like a 0-1 backpack problem.

代码 Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # find sum of array elements
        total_sum = sum(nums)

        # if total_sum is odd, it cannot be partitioned into equal sum subsets
        if total_sum % 2 != 0:
            return False

        subset_sum = total_sum // 2   
        n = len(nums)
        # construct a dp table of size (n+1) x (subset_sum + 1)
        dp = [[False for _ in range(subset_sum + 1)] for _ in range(n+1)]
        dp[0][0] = True
        for i in range(1, n+1):
            curr = nums[i-1] 
            for j in range(subset_sum + 1):
                if j < curr:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-curr]

        return dp[-1][-1]

复杂度分析

DP 时间复杂度： O(len(nums) sum(nums)/2)
空间复杂度：O(len(nums) sum(nums)/2)

[st2yang]

思路

• 0-1背包

代码

• python

  class Solution:
  def canPartition(self, nums: List[int]) -> bool:
      n = len(nums)
      target = sum(nums)
  
      if target % 2 != 0:
          return False
  
      target = int(target / 2)
  
      dp = [False] * (target + 1)
      dp[0] = True
  
      for i in range(n):
          for j in range(target, 0, -1):
              # dp[i][j] = dp[i-1][j] or (j - nums[i] >= 0 and dp[i-1][j - nums[i]])
              dp[j] = dp[j] or (j - nums[i] >= 0 and dp[j - nums[i]])
  
      return dp[target]

复杂度

• 时间: O(mn)
• 空间: O(mn)

[itsjacob]

Intuition

• [tags] 0/1 backpack 2D dynamic-programming program
• given the pack capacity as sum/2, how much can we pack? if we can pack to sum/2, then the original nums can be divided evenly to two halves

Implementation

class Solution
{
public:
  bool canPartition(vector<int> &nums)
  {
    int sumOfNums = std::accumulate(nums.begin(), nums.end(), 0);
    if (sumOfNums % 2 != 0) return false;
    int halfSum = sumOfNums / 2;
    // dp[jj][ii] represents the total value from first jj nums given our bag capacity is ii
    std::vector<std::vector<int>> dp(nums.size() + 1, std::vector<int>(halfSum + 1, 0));
    for (int jj = 1; jj <= nums.size(); jj++) {
      for (int ss = 1; ss <= halfSum; ss++) {
        if (nums[jj - 1] > ss) {
          // current num exceeds the bag capacity
          dp[jj][ss] = dp[jj - 1][ss];
        } else {
          // pack as much as we can
          dp[jj][ss] = std::max(dp[jj - 1][ss - nums[jj - 1]] + nums[jj - 1], dp[jj - 1][ss]);
        }
      }
    }
    return dp[nums.size()][halfSum] == halfSum;
  }
};

Complexity

• Time complexity: O(mn), where m = sum/2
• Space complexity: O(mn), where m = sum/2

[ghost]

题目

416. Partition Equal Subset Sum

思路

DP

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target%2 == 1: return False
        else: target = target//2
        n = len(nums)

        dp = [False] * (target+1)
        dp[0] = True

        for i in range(n-1):
            for j in range(target, nums[i]-1, -1):
                    dp[j] = dp[j] or dp[j-nums[i]]

        return dp[target]

复杂度

Space: O(m) Time: O(m*n)

[L-SUI]

/**

• @param {number[]} nums
• @return {boolean} */ var canPartition = function(nums) { const n = nums.length; if (n < 2) { return false; } let sum = 0, maxNum = 0; for (const num of nums) { sum += num; maxNum = maxNum > num ? maxNum : num; } if (sum & 1) { return false; } const target = Math.floor(sum / 2); if (maxNum > target) { return false; } const dp = new Array(target + 1).fill(false); dp[0] = true; for (const num of nums) { for (let j = target; j >= num; --j) { dp[j] |= dp[j - num]; } } return dp[target]; };

[learning-go123]

思路

• 动态规划

代码

• 语言支持：Go

Go Code:

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }

    sum /= 2
    dp := make([]bool, sum+1)
    dp[0] = true
    for i := range nums {
        for j := sum; j >= 1; j-- {
            if j-nums[i] >= 0 {
                dp[j] = dp[j] || dp[j-nums[i]]
            }
        }
    }

    return dp[sum]
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[weichuliao]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)

        if target % 2 != 0:
            return False

        target = int(target / 2)

        dp = [False] * (target + 1)
        dp[0] = True

        for i in range(n):
            for j in range(target, 0, -1):
                dp[j] = dp[j] or (j - nums[i] >= 0 and dp[j - nums[i]])

        return dp[target]

[carterrr]

class 分割等和子集_416_二维dp简化为一维 {
    public boolean canPartition(int[] nums) {
        int target = 0;
        for(int num : nums) {
            target += num;
        }
        if(target % 2 == 1) return false;
        target /= 2;
        boolean[] dp = new boolean[target + 1];  // 和为下标的数字能否凑齐
        dp[0] = true;   // 和为0一定可以选到
        for(int i = 0; i < nums.length; i++) { // 从第0 个数开始选
            for(int j = target; j>= nums[i]; j-- ){ // 倒序更新 避免dp[j-nums[i]] 先被计算出来  影响结果
                dp[j] |= dp[j-nums[i]];  // 看作 选这个数或者不选这个数字 不选就是dp[i-1][j] 选就是  dp[i-1][j-nums[i]]
            }
        }
        return dp[target];
    }
}

[tongxw]

01背包

• dp(i, j): 数组前i个数的和是否为j
• 初始状态：dp(0, nums[0]) = true，其他为false

• 转移方程：选nums[i]或者不选，只要其中一种情况为true，那么dp(i, j)就为true，即 dp(i, j) = dp(i-1, j) || dp(i-1, j - nums[i])

  public boolean canPartition(int[] nums) {
    int n = nums.length;
    int sum = Arrays.stream(nums).sum();
    if ((sum & 1) == 1) {
      return false;
    }
  
    int target = sum / 2;
    boolean[][] dp = new boolean[n][target + 1];
    if (target >= nums[0]) {
      dp[0][nums[0]] = true;
    }
  
    for (int i=1; i<n; i++) {
      for (int j=0; j<=target; j++) {
        dp[i][j] = dp[i-1][j] || (j >= nums[i] && dp[i-1][j-nums[i]]);
      }
    }    
    return dp[n-1][target];
  }

• TC: O(len(num) * sum(num))
• SC: O(len(num) * sum(num))

[siyuelee]

暴力

class Solution(object):
    def canPartition(self, nums):
        if sum(nums) % 2:
            return False
        if max(nums) > sum(nums) / 2:
            return False
        target = sum(nums) / 2
        def dfs(nums, target, cur):
            if target < 0 or cur >= len(nums):
                return False
            else:
                return target == 0 or dfs(nums, target - nums[cur], cur + 1) or dfs(nums, target, cur + 1)
        return dfs(nums, target, 0)

[zjsuper]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums)%2 == 1:
            return False
        target = sum(nums)//2
        dp = [[False for _ in range(target+1)] for _ in range(len(nums))]
        for i in range(len(nums)):
            dp[i][0] = True 
        if nums[0] <= target:
            dp[0][nums[0]] = True 
        for i in range(1,len(nums)):
            for j in range(1,target+1):
                if j > nums[i]:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
                else:
                    dp[i][j] = dp[i-1][j] 

        #print(dp)      

        return dp[-1][-1]

[falconruo]

思路: DP

复杂度：

• 时间复杂度: O(M*N)， 其中M是数组元素之和，N是数组元素个数
• 空间复杂度: O(M)

代码(C++):

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        else
            sum = (sum >> 1);

        vector<bool> dp(sum + 1, false);
        dp[0] = true;

        for (auto & n : nums) {
            for (int i = sum; i >= n; --i)
                dp[i] = dp[i] || dp[i - n];
        }

        return dp[sum];
    }
};

[XinnXuu]

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2){
            return false;
        }
        int sum = 0;
        int maxNum = 0;
        for (int i = 0; i < n; i++){
            sum += nums[i];
            if (nums[i] > maxNum){
                maxNum = nums[i];
            }
        }
        if (sum % 2 != 0){
            return  false;
        }
        int target = sum / 2;
        if (maxNum > target){
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];

        for (int i = 0; i < n; i++){
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++){
            for (int j = 1; j < target + 1; j++){
                if (nums[i] < j){
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                }
                else if (nums[i] == j){
                    dp[i][j] = true;
                    continue;
                }
                else if (nums[i] > j){
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}