azl397985856 commented 2 years ago

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

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

yetfan commented 2 years ago

思路边界：数字可分为两堆，必须大于一个分为两堆相等和为总和的一半target 逐步dp，新加入一个元素i，看其中部分数之和是否可以得到1 - target 1.旧数可以得到，那么新数加进来不用选也可以得到 dp[i][j] = dp[i-1][j] 2.旧数可以得到，加入新数的和也可以得到 dp[i][j+num] = dp[i-1][j] + num 3.空间压缩转移方程 dp[j] = dp[j] ∣ dp[j−nums[i]]

代码

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]

复杂度 时间 O(n*target) 空间 O(target)

wangzehan123 commented 2 years ago

代码

语言支持：Java

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];
    }
}

Rex-Zh commented 2 years ago

思路

学习中，先打个卡

代码

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];
    }
}

CoreJa commented 2 years ago

思路

背包问题的基本思路都忘了，太久没做dp了。回顾一波

背包问题的特征是在原有数组上增加一个维度target，即背包的容量，容量从0到target，考虑的是对于一个新的元素，我们是否要把它加入背包。dp[i][j]表示的是对于容量为j的容量，把0到i的物品中的部分装进去能得到的最大价值，判断的依据是dp[i-1][target-nums[i]]+nums[i]是否比dp[i-1][j]更大。

回到这个题，先算target，即nums的和除2，剩下的就和背包问题一样了，背包问题是价值最大化，这个只要能等于target就行，所以dp里存的布尔值，所以这题还可以用状态压缩加快dp

原始DP：dp[i][j]表示对于target为j的情况下，任取0到i的元素，其和是否为j，在这个定义下可以想到，我可以选用nums[i]或不选，不选那就直接沿用dp[i-1][j]的结果，选那就可以用dp[i-1][j-nums[i]]的结果(局部最优解，表示背包容量比现在少nums[i]的情况下能否满足条件，能那么选用了nums[i]也能)。状态转移方程：$dp[i][j]=dp[i-1][j]\ |\ dp[i-1][j-nums[i]]$，复杂度$O(m*n)$，n为数组长度，m为target。
滚动DP：因为DP更新的过程中仅与上一状态(i-1)相关，所以可以让一维数组滚动更新，而且要注意需要从右往左更新。(后面值的更新依赖前面的值)，状态转移方程$dp[j]=dp[j]\ |\ dp[j-nums[i]]$，复杂度$O(m*n)$
状态压缩DP+位运算：因为DP中的元素均为boolean，所以可以用bitset来替代。同时分析滚动DP的状态转移方程$dp[j]=dp[j]\ |\ dp[j-nums[i]]$分为两个部分，j-nums[i]就相当于是对于nums[i]把整个dp的bitset右移了nums[i]位，状态转移方程变成了$dp\ |\ =dp>>nums[i]$。而这可以将原来计算m次变成一次，复杂度$O(n)$

代码

class Solution:
    # 原始DP：`dp[i][j]`表示对于`target`为`j`的情况下，任取0到`i`的元素，其和是否为`j`，在这个定义下可以想到，我可以选用
    # `nums[i]`或不选，不选那就直接沿用`dp[i-1][j]`的结果，选那就可以用`dp[i-1][j-nums[i]]`的结果(局部最优解，表示背包
    # 容量比现在少nums[i]的情况下能否满足条件，能那么选用了`nums[i]`也能)。状态转移方程：
    # $dp[i][j]=dp[i-1][j]\ |\ dp[i-1][j-nums[i]]$，复杂度$O(m*n)$，n为数组长度，m为target。
    def canPartition1(self, nums: List[int]) -> bool:
        if sum(nums) % 2 == 1:
            return False
        target = sum(nums) // 2
        n = len(nums)
        dp = [[False] * (target + 1) for _ in range(n)]
        # init dp
        for i in range(n):
            dp[i][0] = True
        if nums[0] <= target:
            dp[0][nums[0]] = True
        # generate dp
        for i in range(1, n):
            for j in range(1, target + 1):
                if j < nums[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
        return dp[-1][-1]

    # 滚动DP：因为DP更新的过程中仅与上一状态(i-1)相关，所以可以让一维数组滚动更新，而且要注意需要从右往左更新。(后面值的更
    # 新依赖前面的值)，状态转移方程$dp[j]=dp[j]\ |\ dp[j-nums[i]]$，复杂度$O(m*n)$
    def canPartition2(self, nums: List[int]) -> bool:
        if sum(nums) % 2 == 1:
            return False
        target = sum(nums) // 2
        dp = [True] + [False] * target
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[-1]

    # 状态压缩DP+位运算：因为DP中的元素均为boolean，所以可以用bitset来替代。同时分析滚动DP的状态转移方程
    # $dp[j]=dp[j]\ |\ dp[j-nums[i]]$分为两个部分，`j-nums[i]`就相当于是对于`nums[i]`把整个dp的bitset右移了`nums[i]`
    # 位，状态转移方程变成了$dp\ |\ =dp>>nums[i]$。而这可以将原来计算`m`次变成一次，复杂度$O(n)$
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target & 1:
            return False
        cur = 1 << target // 2
        for i in range(len(nums)):
            cur |= cur >> nums[i]
        return cur & 1 == 1

laofuWF commented 2 years ago

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]

ZhangNN2018 commented 2 years ago

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        n=len(nums)
        sum = 0
        for num in range(0,n):
            sum += nums[num]
        # 和为奇数时，不可能划分成两个和相等的集合
        if sum % 2 != 0:
            return False
        sum = sum / 2
        dp = [False]*(sum+1)

        # base case
        dp[0] = True
        for i in range(0,n):
            for j in reversed(range(sum+1)):
                if (j - nums[i] >= 0):
                    dp[j] = dp[j] or dp[j - nums[i]]
        return dp[sum]

LinnSky commented 2 years ago

思路

动态规划

代码

     var canPartition = function(nums) {
        let sum = nums.reduce((pre, cur) => pre + cur);
        if (sum % 2 != 0) return false;
        let n = nums.length;
        sum = sum / 2;
        let dp = new Array(n + 1)
            .fill(false)
            .map(() => new Array(sum + 1).fill(false));
        for (let i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= sum; j++) {
          if (j - nums[i - 1] < 0) {
              dp[i][j] = dp[i - 1][j];
          } else {
              dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
          }
          }
      }
      return dp[n][sum];
  };

ZacheryCao commented 2 years ago

Idea

Dp + backpack

Code

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

Complexity:

Time: O(N * sum) Space: O(sum)

yan0327 commented 2 years ago

func canPartition(nums []int) bool {
    sum := 0
    for _,x := range nums{
        sum += x
    }
    if sum % 2 != 0{
        return false
    }
    sum /= 2
    dp := make([]bool,sum+1)
    dp[0] = true
    for _,num := range nums{
        for i:=sum;i>=num;i--{
            dp[i] = dp[i]||dp[i-num]
        }
    }
    return dp[sum]
}

xinhaoyi commented 2 years ago

416. 分割等和子集

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

思路一

dfs递归

超时了

代码

//方法一 dfs 这个方法会超时，我们要改进一下它，比如把数字从小到大排序一下，结果发现还是会超时
class Solution {
    public boolean canPartition(int[] nums) {
        //dfs递归
        //我们顺着遍历数组，注意每一个数都有被丢出去到新堆中，和留下来在老堆中两种可能
        //我们从数组中取出一个数，newTotal += 这个数，leftTotal -= 这个数
        //或者也可以不取，那么就只是下标增加，别的都不变
        //newTotal指新数组的和，leftTotal指老数组剩余数的和
        //看他们等不等，不能的话如果newTotal < leftTotal就继续取数，否则就直接false，因为再怎么取都没有意义了
        //这种取法问题出在前面，再往后取肯定一直是newTotal > leftTotal，所以直接false

        //求和
        int total = 0;
        for(int num : nums){
            total += num;
        }

        return dfs(nums, 0, total, 0);

    }
    public boolean dfs(int[] nums, int pos, int leftTotal, int newTotal){
        if(pos == nums.length){
            //因为我们可以永远不把数丢到新堆，所以这里pos要加一个限制
            return false;
        }
        int leftTotalIfOut = leftTotal - nums[pos];
        int newTotalIfOut = newTotal + nums[pos];
        if(leftTotal == newTotal){
            return true;
        }
        else if(leftTotal < newTotal){
            return false;
        }
        else{
            //leftTotal > newTotal
            //我们永远可以选择把这个数丢到新堆，也可以把它留下来
            return dfs(nums,pos + 1,leftTotalIfOut,newTotalIfOut) || dfs(nums,pos + 1,leftTotal,newTotal);
        }
    }
}

思路二

转换成01背包问题

参考思路

动态规划（转换为 0-1 背包问题） - 分割等和子集 - 力扣（LeetCode） (leetcode-cn.com)

状态转移方程

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

进一步写为

dp[i][j] = dp[i - 1][j]    //至少是这个结果
dp[i][j] = true;           //nums[i] = j
dp[i][j] = dp[i - 1][j - nums[i]]   //nums[i] < j

代码

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;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        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] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}

Aobasyp commented 2 years ago

思路动态规划

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)

xuhzyy commented 2 years ago

思路

动态规划,0-1背包问题

代码

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n < 2:
            return False

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

        target = total // 2
        dp = [0] * (target + 1)
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j-num] + num)
        return dp[target] == target

复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(n)

falconruo commented 2 years ago

思路:

动态规划

复杂度分析:

时间复杂度: O(N * target)，N为数组nums长度, target为总和的一半
空间复杂度: O(target)

代码(C++):

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

        for (auto n : nums)
            sum += n;

        if (sum % 2) return false;
        else
            sum = sum >> 1;

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

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

        return dp[sum];
    }
};

ZJP1483469269 commented 2 years ago

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

        if su % 2:
            return False
        tar = su // 2
        vis = [0] * len(nums)
        dp = [None] * (su + 10)
        def dfs(tar):
            if dp[su//2 + tar] != None:
                return dp[su// 2 + tar]
            if tar == 0:
                dp[su//2] = True
                return True
            ans = False

            for i in range(len(nums)):
                if not vis[i]:
                    vis[i] = 1
                    ans |= dfs(tar - nums[i])
                    vis[i] = 0
                if ans:
                    dp[su // 2 + tar] = True
                    return True
            dp[su // 2 + tar] = False
            return ans
        return dfs(tar)

vuesch commented 2 years ago

代码

var canPartition = function (nums) {
  let sum = nums.reduce((acc, num) => acc + num, 0);
  if (sum % 2) {
    return false;
  }
  sum = sum / 2;
  return dfs(nums, sum, 0);
};

function dfs(nums, target, cur) {
  if (target < 0 || cur > nums.length) {
    return false;
  }
  return (
    target === 0 ||
    dfs(nums, target - nums[cur], cur + 1) ||
    dfs(nums, target, cur + 1)
  );
}

复杂度分析

时间：O(n*m)O(n∗m)
空间：O(n)

haixiaolu commented 2 years ago

思路

DP [0-1背包]

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

        dp = set()
        dp.add(0)
        target = sum(nums) // 2

        for i in range(len(nums) - 1, -1, -1):
            nextDP = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True 
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP

        return True if target in dp else False

复杂度分析：

时间复杂度： O(sum(n)), n为数组的长度
空间复杂度： O(sum(n))

Yrtryannn commented 2 years ago

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];
    }
}

rzhao010 commented 2 years ago

   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];

        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] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }    
        }
        return dp[len - 1][target];
    }

RocJeMaintiendrai commented 2 years ago

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;
    }
}

zhangzz2015 commented 2 years ago

思路

如果可以分成两个部分，则表面每个部分相等，先计算出sum，如果sum为奇数，则不能分，如果为偶数，则可分，每部分为sum/2，转化为背包问题。从num中找到正好装满背包。定义dp[i][j] 为从 num 中从0到i是否能找到正好专门背包为j。

` class Solution { public: bool canPartition(vector& nums) {

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

    sum = sum/2; 

    // dp[i][k]   dp[i-1][k - nums[i]] || dp[i-1][k]   

    vector<vector<bool>>   dp(nums.size()+1, vector<bool>(sum+1, false)); 
    for(int i=0; i< nums.size(); i++)
    {
        for(int j=0; j<=sum; j++)
        {
            if(j==0)
            {
                dp[i+1][j] = true; 
            }
            else
            {
                if(j-nums[i]>=0)
                   dp[i+1][j] =  dp[i][j-nums[i]] || dp[i][j];
                else
                    dp[i+1][j] = dp[i][j]; 
            }
        }
    }

    return dp[nums.size()][sum]; 

}

}; `

cszys888 commented 2 years ago

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

        dp = [False]*(target + 1)
        # initialize
        dp[0] = True
        if nums[0] <= target:
            dp[nums[0]] = True

        for row in range(1, n):
            for col in range(target,-1,-1):
                if dp[col] == True:
                    continue
                if nums[row] > col:
                    continue
                else:
                    if dp[col - nums[row]] == True or nums[row] == col:
                        dp[col] = True
        return dp[target]

time complexity: O(N*target), where target stands for half of the sum of all elements in nums space complexity: O(target)

Tesla-1i commented 2 years ago

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n < 2:
            return False

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

        target = total // 2
        dp = [0] * (target + 1)
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j-num] + num)
        return dp[target] == target

shamworld commented 2 years ago

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];
};

Bochengwan commented 2 years ago

思路

背包问题，看能否取出和为target的物品们。

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total%2!=0:
            return False

        target = total//2

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

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

复杂度分析

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

1149004121 commented 2 years ago

分割等和子集

思路

背包问题。

代码

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

复杂度分析

时间复杂度：O(n * sum )。
空间复杂度：O(sum)。

LannyX commented 2 years ago

思路

背包

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for(int n : nums){
            sum += n;
        }
        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[len][target + 1];
        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];
    }
}

复杂度分析

时间复杂度：O(nm)
空间复杂度：O(nm)

tongxw commented 2 years ago

思路

01背包

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        int n = nums.length;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i=1; i<=n; i++) {
            for (int j=target; j>=0; j--) {
                if (!dp[j]) {
                    dp[j] = j >= nums[i-1] && dp[j-nums[i-1]];
                }
            }
        }

        return dp[target];
    }
}

TC: O(n * sum(num)) SC: O(sum(num))

zol013 commented 2 years ago

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

        memo = {}
        def dfs(nums, target, curr):
            if (target, curr) in memo:
                return memo[(target, curr)]
            if target < 0 or curr >= len(nums):
                memo[(target, curr)] = False
                return False

            if target == 0:
                memo[(target, curr)] = True
                return True

            memo[(target, curr)] = dfs(nums, target - nums[curr], curr + 1) or dfs(nums, target, curr + 1)
            return memo[(target, curr)]

        return dfs(nums, summ / 2, 0)

baddate commented 2 years ago

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

JudyZhou95 commented 2 years ago

代码

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

        if target %2 == 1:
            return False

        target >>=1

        dp = [True] + [False]*target

        for n in nums:
            dp = [dp[j] or (j >= n and dp[j-n]) for j in range(target+1)]
            if dp[target]: return True

        return False

ivangin commented 2 years ago

0/1背包

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];

    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] = true;
                continue;
            }
            if (nums[i] < j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
            }
        }
    }
    return dp[len - 1][target];
}

alongchong commented 2 years ago

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];
    }
}

charlestang commented 2 years ago

思路

题目的本质是一个 0-1 背包问题。

能否从数组中找到一些数字，正好凑够总和的一半。

时间复杂度 O(n^2)

空间复杂度O(n^2)

代码

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

        allSum = sum(nums)
        target = allSum // 2

        if allSum % 2 != 0: return False

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

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

        return dp[n][target]

zwx0641 commented 2 years ago

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

    boolean[][] dp = new boolean[nums.length + 1][target + 1];
    dp[0][0] = true;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j <= target; j++) {
            if (j < nums[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[nums.length - 1][target];
}

}

stackvoid commented 2 years ago

思路

不会，看答案。。。

代码

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;
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
        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] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}

复杂度分析

Time O(N) Space O(N)

hdyhdy commented 2 years ago

func canPartition(nums []int) bool {
    n := len(nums)
    if n < 2 {
        return false
    }

    sum, max := 0, 0
    for _, v := range nums {
        sum += v
        if v > max {
            max = v
        }
    }
    if sum%2 != 0 {
        return false
    }

    target := sum / 2
    if max > target {
        return false
    }

    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, target+1)
    }
    for i := 0; i < n; i++ {
        dp[i][0] = true
    }
    dp[0][nums[0]] = true
    for i := 1; i < n; i++ {
        v := nums[i]
        for j := 1; j <= target; j++ {
            if j >= v {
                dp[i][j] = dp[i-1][j] || dp[i-1][j-v]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[n-1][target]
}

Toms-BigData commented 2 years ago

func canPartition(nums []int) bool { n := len(nums) if n < 2 { return false }

sum, max := 0, 0
for _, v := range nums {
    sum += v
    if v > max {
        max = v
    }
}
if sum%2 != 0 {
    return false
}

target := sum / 2
if max > target {
    return false
}

dp := make([][]bool, n)
for i := range dp {
    dp[i] = make([]bool, target+1)
}
for i := 0; i < n; i++ {
    dp[i][0] = true
}
dp[0][nums[0]] = true
for i := 1; i < n; i++ {
    v := nums[i]
    for j := 1; j <= target; j++ {
        if j >= v {
            dp[i][j] = dp[i-1][j] || dp[i-1][j-v]
        } else {
            dp[i][j] = dp[i-1][j]
        }
    }
}
return dp[n-1][target]

}

spacker-343 commented 2 years ago

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

CodingProgrammer commented 2 years ago

思路

01 背包问题

代码

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        // 和不能被 2 整除，返回 false
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        // dp[i][j] 表示将 [0,i] 上的数字放入容量为 j 的子集所能形成最大和
        int[] dp = new int[target + 1];

        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                if (dp[target] == target) return true;
            }
        }

        return dp[target] == target;
    }
}

复杂度

Time : O(N * Sum / 2) Sum 为数组的和
Space: O(Sum / 2)

Riuusee commented 2 years ago

思路

动态规划。状态转移方程： dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

代码

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

        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] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
}

复杂度分析

时间复杂度: O(n*target),target为数组和一半
空间复杂度: O(n*target)

biscuit279 commented 2 years ago

思路：

动态规划，dp[i][j]表示前[i]个数是否包含和为[j]的子数组

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n<2:
            return False
        total = sum(nums)
        maxNum = max(nums)
        if total % 2 == 1:
            return False
        target = total // 2
        if maxNum > target:
            return False
        dp = [[False]*(target+1) for _ in range(n)] #dp[i][j]表示从前i个数中是否可以选择出一个和为j的子序列
        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]

时间复杂度：O(ntarget) 空间复杂度：O((ntarget)

moirobinzhang commented 2 years ago

Code:

public class Solution { public bool CanPartition(int[] nums) { if (nums == null || nums.Length == 0) return false;

    int sum = 0;
    foreach(int item in nums)
        sum += item;

    if (sum % 2 != 0 )
        return false;

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

    foreach(int num in nums)
    {
        for(int i = sum; i>=num; i--)
        {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[sum];
}

}

GaoMinghao commented 2 years ago

思路

背包问题

代码

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

callmeerika commented 2 years ago

思路

看的题解= =

代码

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(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]] = true;
    for (let i = 1; i < n; i++) {
        const num = nums[i];
        for (let 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];
};

复杂度

时间复杂度：O(n*target)
空间复杂度：O(target)

Flower-F commented 2 years ago

思路

01 背包

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
  let sum = nums.reduce((prev, cur) => prev + cur);
  if (sum % 2 !== 0) {
    return false;
  }

  sum = sum / 2;

  const dp = new Array(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(MN) 空间：O(N)

MissNanLan commented 2 years ago

代码

语言支持：JavaScript

JavaScript Code:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
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];
};

复杂度分析

令 n 为数组长度。

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

bluetomlee commented 2 years ago

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxNum = *max_element(nums.begin(), nums.end());
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        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];
    }
};

Today-fine commented 2 years ago

揣摩动态规划中


class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        // 计算总和
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 拿到最大的元素，返回的是一个指针迭代器，需要解引用
        int maxNum = *max_element(nums.begin(), nums.end());
        // 按位与 如果 二进制第一位不是0 就说明是单数
        if (sum & 1) {
            return false;
        }
        // 拿到中间值
        int target = sum / 2;

        if (maxNum > target) {
            return false;
        }

        vector<vector<int> > dp(n, vector<int>(target + 1, 0));
        // 动态规划
        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];
    }
};

zzzpppy commented 2 years ago

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length, sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 != 0) return false;
        int m = sum / 2;
        boolean[][] f = new boolean[n + 1][m + 1];
        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];
    }
}

Myleswork commented 2 years ago

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

leetcode-pp / 91alg-6-daily-check

【Day 61 】2022-02-10 - 416. 分割等和子集 #71

416. 分割等和子集

入选理由

题目地址

前置知识

题目描述

代码

思路

代码

思路

代码

思路

代码

Idea

Code

Complexity:

416. 分割等和子集

思路一

代码

思路二

代码

思路

代码

代码

复杂度分析

思路

复杂度分析：

思路

思路

代码

思路

代码

思路

代码

思路

代码

思路

代码

复杂度分析

思路

代码

复杂度

思路

代码

思路：

思路

代码

思路

代码

复杂度

思路

代码

复杂度

代码