【Day 61 】2022-12-31 - 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

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

[tiandao043]

思路

一开始以为是dfs，看了题解dp，dp[i][j]表示第i个nums下能否构成j值，dp[i][target]=dp[i-1][target-nums[i]]||dp[i-1][target], 记 F[i, target] 为 nums 数组内前 i 个数能否构成和为 target 的子序列的可能，则状态转移方程为 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // sort(nums.begin(),nums.end());
        int sum=0;
        for(auto num:nums){
            sum+=num;
        }
        if(sum%2)return false;
        sum/=2;
        int n=nums.size();
        vector<vector<bool>> dp(n,vector<bool>(sum+1));
        for(int i=0;i<n;i++){
            dp[i][0]=true;
        }

        for(int i=0;i<n-1;i++){            
            for(int j=0;j<sum+1;j++){
                // cout<<nums[i]<<endl;
                if(j<nums[i]){
                    dp[i+1][j]=dp[i][j];
                }else{
                    dp[i+1][j]=dp[i][j-nums[i]]||dp[i][j];
                }
            }
        }
        return dp[nums.size()-1][sum];
    }
};

O(n×target)

[Ryanbaiyansong]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 只有正数的数组, 分割成两个等和的子集
        # 题目转化 => 相当于找到一个子序列, 子序列的和为sum // 2
        tot = sum(nums)
        n = len(nums)
        if tot % 2:
            return False

        target = tot // 2

        # @cache
        # def dfs(i:int, acc:int) -> bool:
        #     if acc == target:
        #         return True 
        #     if i == n:
        #         return False
        #     if acc > target:
        #         return False

        #     # 选择当前的数字
        #     choice1 = dfs(i + 1, acc + nums[i])
        #     # 不选择当前的数字
        #     choice2 = dfs(i + 1, acc)

        #     return choice1 or choice2 

        # return dfs(0, 0)

        # 时间复杂度: 2**N

        # f = [[False] * (target + 1) for _ in range(n + 1)]
        # f[0][0] = True
        # for i in range(1, n + 1):
        #     for j in range(target + 1):
        #         # 如果不选当前元素
        #         f[i][j] = f[i-1][j]
        #         # 如果选择当前元素
        #         if j - nums[i-1] >= 0:
        #             f[i][j] |= f[i-1][j - nums[i-1]]
        # return f[-1][-1]

        # 压缩到一维
        f = [False] * (target + 1)
        f[0] = True

        for i, x in enumerate(nums):
            for j in range(target, x - 1, -1):
                f[j] |= f[j - x]

        return f[-1]

[zjsuper]

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

dp[first n nums][target] = dp[first n-1 nums][target] or dp[first n-1 nums][target-nums[n]]

    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,int(target+1)):
            if nums[i] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
            else:
                dp[i][j] = dp[i-1][j]  
    return dp[-1][-1]

[snmyj]

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

    return f[sum];

    }
};

[buer1121]

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

    n=len(nums)
    target=sum(nums)
    if target%2 !=0: return False
    target=target//2
    #10001是因为200个100的总和为20000
    dp=[0]* 10001
    for i in range(n):
        for j in range(target,nums[i] - 1,-1):
             dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
    return target==dp[target]

[zywang0]

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

    return f[sum];

    }
};

[mayloveless]

思路

求合取一半设置为目标值，题目转化为哪些数组合等于目标值。 状态转移方程：第i个数字决策完成之后，和为target这种状态是否成立

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = _.sum(nums);
    if (sum%2 === 1) {
        return false
    }

    const target = sum/2;
    const n = nums.length;
    // 数组元素和目标和的一个大表格
    // 每个值的含义是：第i个数字决策完成之后，和为target这种状态是否成立
    const dp = Array(n).fill().map(() => Array(target+1).fill(false))   
    dp[0][0] = true;
    // 初始值
    if (nums[0] <= target) {
        dp[0][nums[0]] = true
    }

    for(let i =1 ;i<n;i++) {
        for(let j =0 ;j<=target;j++) {
            if (j >= nums[i]) {
                // 选还是不选
                dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];
            } else {
                // 不选
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n-1][target];// 返回第n个元素，和为target的状态
};

复杂度

时间：O(ntarget) 空间：O(ntarget)

[RestlessBreeze]

code

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

[jackgaoyuan]

func canPartition(nums []int) bool {
    //画一个二维表格， 就清晰了
    sum := 0
    for _, v := range nums {
        sum += v
    }
    if sum % 2 != 0 {
        return false
    }
    m := len(nums)
    target := sum / 2
    dp := make([][]bool, m + 1)
    for i := 0; i < m + 1; i++ {
        dp[i] = make([]bool, target + 1)
    }

    for i := 0; i < m + 1; i++ {
        dp[i][0] = true
    }
    for i := 1; i < m + 1; i++ {
        for j := 0; j < target + 1; 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]
            }
        }
    }
    return dp[m][target]
}

[A-pricity]

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
 // 这道题可以转化成一个求容量为sum / 2的背包问题，若正好可以填满背包，就返回true
  const sum = nums.reduce((a, b) => a + b)
  const len = nums.length
  if (sum % 2 || len < 2) {
      return false
  }
  const half = sum / 2
  const res = []
  for (let i = 0; i < half + 1; i++) {
    res[i] = nums[0] <= i ? nums[0] : 0
  }
  for (let i = 1; i < len; i++) {
    for (let j = half; j >= nums[i]; j--) {
        // 更新不同物品放入的数字最大和        
        res[j] = Math.max(res[j], nums[i] + res[j - nums[i]])
    }
  }
  // 如果背包正好填满则返回true
  return res[half] === half
};

[Jetery]

416. 分割等和子集

思路

动态规划

代码 (cpp)

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

复杂度分析

• 时间复杂度：O(n * sum / 2)
• 空间复杂度：O((n * sum / 2)

[paopaohua]

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[target + 1];
        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];
    }
}

[Alexno1no2]

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

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

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

[FlipN9]

/**
    TC: O(N)    SC: O(1)
*/
import java.math.BigInteger;

public class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) 
            total += num;

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

        BigInteger state = BigInteger.ONE;

        for (int num : nums) 
            state = state.or(state.shiftLeft(num));

        return state.testBit(total / 2);
    }
}

[whoam-challenge]

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]

[Elsa-zhang]

# 416. 分割等和子集
''' 背包
'''
class Solution:
    def canPartition(self, nums: list[int]):

        if len(nums) < 2:
            return False

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

        target = total // 2

        maxNum = max(nums)
        if maxNum > target:
            return False

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

        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] | dp[i - 1][j - nums[i]]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[len(nums)-1][target]

nums = [1,5,11,5]
solution = Solution()
ans = solution.canPartition(nums)
print(ans)

[klspta]

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[target + 1];
        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];
    }
}

[chenming-cao]

解题思路

动态规划。首先求数组和sum，如果和为奇数，必然无法分成两个等和子集，返回false。如果和为偶数，则考虑是否需要将对应元素放入子集中从而达到和为sum/2。此题便转化为0-1背包问题。用二维数组表示状态，dp[i][j]表示能否用下标从0到i的元素达到和为j。状态转移方程：对于dp[i][j]，考虑不选当前元素nums[i]，则结果为dp[i - 1][j]；如果选择当前元素nums[i]，则结果为dp[i - 1][j - nums[i]]，注意j >= nums[i]。两者做或运算即为dp[i][j]结果。遍历数组按照下标从小到大顺序填表，最后返回结果dp[nums.length - 1][sum / 2]即可。

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // if sum is odd, the array cannot be partitioned into two subsets
        if (sum % 2 == 1) return false;

        // convert to 0-1 Knapsack problem
        int target = sum / 2;
        int len = nums.length;
        // dp[i][j] represents whether we can use elements from index 0 to i to form a subset with sum j
        boolean[][] dp = new boolean[len][target + 1];
        // fill in base case
        for (int i = 0; i < len; i++) {
            dp[i][0] = true; // if sum is 0, we can form a subset without any elements
        }

        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= target; j++) {
                // consider whether choosing nums[i] or not
                dp[i][j] = j >= nums[i] ? dp[i - 1][j - nums[i]] || dp[i - 1][j] : dp[i - 1][j];
            }
        }
        return dp[len - 1][target];
    }
}

复杂度分析

• 时间复杂度：O(m * n)，m为sum / 2，n为数组长度
• 空间复杂度：O(m * n)

[bookyue]

code

1. memorization search
2. bottom up dp

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;

        if ((sum & 1) == 1) return false;

        return dfs(nums, sum / 2, 0, new Boolean[nums.length][sum / 2 + 1]);
    }

    private boolean dfs(int[] nums, int sum, int index, Boolean[][] dp) {
        if (index == nums.length || sum < 0) return false;

        if (dp[index][sum] != null) return dp[index][sum];

        if (sum == 0) {
            dp[index][sum] = true;
            return true;
        }

        for (int i = index; i < nums.length; i++) {
            if (dfs(nums, sum - nums[i], i + 1, dp)) {
                dp[i][sum] = true;
                return true;
            } else 
                dp[i][sum] = false;
        }

        dp[index][sum] = false;
        return dp[index][sum];
    }

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

        int n = nums.length;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];

        dp[0] = true;

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

        return dp[target];
    }