Formatted question description: https://leetcode.ca/all/416.html

416. Partition Equal Subset Sum

Level

Medium

Description

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

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

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

Example 2:

Input: [1, 2, 3, 5]

Output: false

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

Solution

First, calculate the sum of the elements in the array nums. If this sum is odd, partitioning the array into two subsets with equal sums is impossible, so the function should return false.

Define length as the length of the array nums and target as half the sum of the elements in nums. Employ dynamic programming to solve this problem. Construct a 2D boolean array dp with length rows and target + 1 columns. Here, dp[i][j] indicates the feasibility of selecting a subset from the first i elements of nums that sums up to j, where j ranges from 0 to target. Initialize the first column (column 0) of each row to true, reflecting that a sum of 0 can always be achieved by selecting no elements. Also, set dp[0][nums[0]] to true, acknowledging that the first element can form a subset sum equal to its value.

For each element i from 1 to length - 1, and for every potential sum j from 1 to target, update dp[i][j]. Set it to true if either dp[i - 1][j] is true (the sum j was achievable without the current element) or if dp[i - 1][j - num] is true and j >= num (indicating that adding the current element num to a previously achievable sum of j - num makes j achievable).

The process iterates through the array, progressively building up the solution to larger problems based on the solutions to smaller problems. If dp[length - 1][target] is true, this indicates that it is possible to partition the array into two subsets with equal sums, so the function returns true. Otherwise, it returns false.

import java.util.Arrays;

public class Partition_Equal_Subset_Sum {

    public static void main(String[] args) {
        Partition_Equal_Subset_Sum out = new Partition_Equal_Subset_Sum();
        Solution s = out.new Solution();

        System.out.println(s.canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(s.canPartition(new int[]{1, 2, 3, 5}));
    }

    class Solution {
        public boolean canPartition(int[] nums) {

            if (nums == null || nums.length == 0) {
                return false;
            }

            // in case overflow, should use long
            int sum = sum = Arrays.stream(nums).sum();

            if (sum % 2 != 0) { // two equal subsets, then sum must be 2*x
                return false;
            }

            int target = sum / 2;

            // dp[i] 表示原数组是否可以取出若干个数字，其和为i
            boolean[] dp = new boolean[target + 1];
            dp[0] = true;

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

            }

            return dp[target];
        }
    }


    class Solution_Bitset {

        /*
                bool canPartition(vector<int>& nums) {
                    bitset<5001> bits(1);
                    int sum = accumulate(nums.begin(), nums.end(), 0);
                    for (int num : nums) bits |= bits << num;
                    return (sum % 2 == 0) && bits[sum >> 1];
                }

         */
    }

    // only when subset has 2 elements
    class Solution_2sum {
        public boolean canPartition(int[] nums) {

            if (nums == null || nums.length == 0) {
                return false;
            }

            // in case overflow
            long sum = Arrays.stream(nums).reduce(0, (x, y) -> (x + y));
            if (sum % 2 == 1) {
                return false; // two equal subsets, then sum must be 2*x
            }

            // then it's 2Sum question to sum/2
            Two_Sum twoSum = new Two_Sum();
            Two_Sum.Solution twoSumSolution = twoSum.new Solution();
            Arrays.sort(nums);

            // possible overflow
            return twoSumSolution.twoSum(nums, (int)sum/2) == null;
        }
    }
}


//////

class Solution {
    public boolean canPartition(int[] nums) {
        int s = 0;
        for (int v : nums) {
            s += v;
        }
        if (s % 2 != 0) {
            return false;
        }
        int n = s >> 1;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int v : nums) {
            for (int j = n; j >= v; --j) {
                dp[j] = dp[j] || dp[j - v];
            }
        }
        return dp[n];
    }
}

// OJ: https://leetcode.com/problems/partition-equal-subset-sum/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
public:
    bool canPartition(vector<int>& A) { 
        int total = accumulate(begin(A), end(A), 0);
        if (total % 2) return false;
        unordered_set<int> s, next;
        for (int n : A) {
            next = s;
            for (int m : s) next.insert(m + n);
            next.insert(n);
            if (next.count(total / 2)) return true;
            swap(s, next);
        }
        return false;
    }
};

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


class Solution: # recursive, but over time limit in OJ
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target_sum = total_sum // 2
        memo = {} # ==> or just use @cache for dfs()

        def dfs(idx, curr_sum):
            if curr_sum == target_sum:
                return True
            if curr_sum > target_sum or idx >= len(nums):
                return False
            if (idx, curr_sum) in memo:
                return memo[(idx, curr_sum)]

            # Explore two options: include the current number or exclude it
            include = dfs(idx + 1, curr_sum + nums[idx])
            exclude = dfs(idx + 1, curr_sum)

            memo[(idx, curr_sum)] = include or exclude
            return memo[(idx, curr_sum)]

        return dfs(0, 0)

############

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        m, mod = divmod(sum(nums), 2)
        if mod:
            return False
        f = [True] + [False] * m
        for x in nums:
            for j in range(m, x - 1, -1):
                f[j] = f[j] or f[j - x]
        return f[m]

func canPartition(nums []int) bool {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s%2 != 0 {
		return false
	}
	n := s >> 1
	dp := make([]bool, n+1)
	dp[0] = true
	for _, v := range nums {
		for j := n; j >= v; j-- {
			dp[j] = dp[j] || dp[j-v]
		}
	}
	return dp[n]
}

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
    let s = 0;
    for (let v of nums) {
        s += v;
    }
    if (s % 2 != 0) {
        return false;
    }
    const m = nums.length;
    const n = s >> 1;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= m; ++i) {
        for (let j = n; j >= nums[i - 1]; --j) {
            dp[j] = dp[j] || dp[j - nums[i - 1]];
        }
    }
    return dp[n];
};

function canPartition(nums: number[]): boolean {
    const s = nums.reduce((a, b) => a + b, 0);
    if (s % 2 === 1) {
        return false;
    }
    const m = s >> 1;
    const f: boolean[] = Array(m + 1).fill(false);
    f[0] = true;
    for (const x of nums) {
        for (let j = m; j >= x; --j) {
            f[j] = f[j] || f[j - x];
        }
    }
    return f[m];
}

impl Solution {
    #[allow(dead_code)]
    pub fn can_partition(nums: Vec<i32>) -> bool {
        let mut sum = 0;
        for e in &nums {
            sum += *e;
        }

        if sum % 2 != 0 {
            return false;
        }

        let n = nums.len();
        let m = (sum / 2) as usize;
        let mut dp: Vec<Vec<bool>> = vec![vec![false; m + 1]; n + 1];

        // Initialize the dp vector
        dp[0][0] = true;

        // Begin the actual dp process
        for i in 1..=n {
            for j in 0..=m {
                dp[i][j] = if nums[i - 1] as usize > j {
                    dp[i - 1][j]
                } else {
                    dp[i - 1][j] || dp[i - 1][j - nums[i - 1] as usize]
                }
            }
        }

        dp[n][m]
    }
}

416 - Partition Equal Subset Sum

416. Partition Equal Subset Sum

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

416. Partition Equal Subset Sum

Level

Description

Solution

All Problems

All Solutions