LeetCode 416 - Partition Equal Subset Sum

Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks
Related: Partition of a set into K subsets with equal sum
Extend - Partition of a set into K subsets with equal sum + 3|K Partition Problem
LeetCode 698 - Partition to K Equal Sum Subsets
https://leetcode.com/problems/partition-equal-subset-sum/

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:
Both the array size and each of the array element will not exceed 100.

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.

X. DP
https://leetcode.com/problems/partition-equal-subset-sum/discuss/90592/01-knapsack-detailed-explanation

This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).

Actually, this is a 0/1 knapsack problem, for each number, we can pick it or not. Let us assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.

Base case: dp[0][0] is true; (zero number consists of sum 0 is true)

Transition function: For each number, if we don't pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i]). If we pick nums[i]. dp[i][j] = dp[i-1][j-nums[i]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

talking is cheap:

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

    int n = nums.length;
    boolean[][] dp = new boolean[n+1][sum+1];
    for (int i = 0; i < dp.length; i++) {
        Arrays.fill(dp[i], false);
    }
    
    dp[0][0] = true;
    
    for (int i = 1; i < n+1; i++) {
        dp[i][0] = true;
    }
    for (int j = 1; j < sum+1; j++) {
        dp[0][j] = false;
    }
    
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < sum+1; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i-1]) {
                dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
            }
        }
    }
   
    return dp[n][sum];
}

But can we optimize it? It seems that we cannot optimize it in time. But we can optimize in space. We currently use two dimensional array to solve it, but we can only use one dimensional array.

So the code becomes:

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

http://www.cnblogs.com/grandyang/p/5951422.html

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

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

https://discuss.leetcode.com/topic/62307/java-short-dp-solution-with-explanation

If sum of all the numbers is odd, the surely we cannot reach equal partition.

Using a boolean dp array (limit its max index to sum/2) whose ith entry indicates there is a way to reach the value i using certain subset of the numbers. SO if at any time we can find a subset to reach sum/2 index, we are able to equally partition.

Disclaimer: logic borrowed from https://chinmaylokesh.wordpress.com/2011/02/10/balanced-partition-problem-finding-the-minimized-sum-between-two-partitions-of-a-set-of-positive-integers/

https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

Since the problem is a 0-1 backpack problem, we only have two choices which are take or not. Thus in this problem, by using the sum value as the index of DP array, we transfer the problem to "whether should we take the currently visited number into the sum or not".
To construct the DP recurrence, when we are visiting nums[i] and to find partition of sum j: if we do not take the nums[i], then the current iteration does not make any difference on current DP value; if we take the nums[i], then we need to find whether the (new_sum = j - nums[i]) can be constructed. If any of this two construction can work, the partition of sum == j can be reached.

You can check for success within your elements loop (outer loop) to possibly terminate early.

Second, you can start your dp loop (inner loop) from a "max" position which is the lesser of the current sum of all elements used so far or the dp length.

    public bool CanPartition(int[] nums) 
    {
        int sum = 0;
        for (int i = 0; i < nums.Length; i++) sum += nums[i];
        int target = sum / 2;
        if (target * 2 != sum) return false;
        
        bool[] dp = new bool[target + 1];
        dp[0] = true;

        int currSum = 0;        
        foreach (int x in nums)
        {
            int max = Math.Min(currSum + x, target);
            for (int j = max; j >= x; j--)
            {
                dp[j] = dp[j] || dp[j-x];
            }
            
            if (dp[target] == true) return true;
            currSum += x;
        }
        
        return dp[target];
    }

    public boolean canPartition(int[] nums) {
        // check edge case
        if (nums == null || nums.length == 0) {
            return true;
        }
        // preprocess
        int volumn = 0;
        for (int num : nums) {
            volumn += num;
        }
        if (volumn % 2 != 0) {
            return false;
        }
        volumn /= 2;
        // dp def
        boolean[] dp = new boolean[volumn + 1];
        // dp init
        dp[0] = true;
        // dp transition
        for (int i = 1; i <= nums.length; i++) { // if(nums[i-1] > volumn/2) break;
            for (int j = volumn; j >= nums[i-1]; j--) {//\\
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[volumn];
    }

https://discuss.leetcode.com/topic/64499/java-solution-similar-to-subset-sum-problem
http://leetcodesolution.blogspot.com/2016/10/leetcode-partition-equal-subset-sum.html
https://discuss.leetcode.com/topic/62913/38ms-dp-java-solution

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n == 0) 
            return true;
        int sum = 0;
        for (int num: nums) {
            sum += num;
        }
        if (sum % 2 == 1)
            return false;
        Arrays.sort(nums);
        int target = sum / 2;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (nums[i-1] == target)
                return true;
            if (nums[i-1] > target)
                return false;
            System.arraycopy(dp[i-1], 0, dp[i], 0, Math.min(target + 1, nums[i-1]));??
            for (int j = nums[i-1]; j <= target; j++) {
                dp[i][j] = dp[i-1][j - nums[i-1]];
            }
            if (dp[i][target])
                return true;
        }
        return false;
    }

https://discuss.leetcode.com/topic/64499/java-solution-similar-to-subset-sum-problem
It's similar to Subset Sum Problemwhich asks us to find if there is a subset whose sum equals to target value. For this problem, the target value is exactly the half of sum of array.

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num: nums) sum += num;
        if(sum % 2 == 1) return false;
        
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        // deal with the first row
        if(nums[0] <= target) dp[0][nums[0]] = true;
        
        // deal with the first col
        for(int i = 0; i < nums.length; i++) dp[i][0] = true;
        
        // deal with the rest
        for(int i = 1; i < dp.length; i++) {
            for(int j = 1; j < dp[0].length; j++) {
                if(j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

http://bookshadow.com/weblog/2016/10/09/leetcode-partition-equal-subset-sum/

动态规划（Dynamic Programming）

利用数组dp[i]记录和为i的子数组是否存在，初始令dp[0] = 1

for num in nums:
    for i in range(sum(nums) - num + 1):
        if dp[i]: dp[i + num] = 1

def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ sums = sum(nums) if sums & 1: return False nset = set([0]) for n in nums: for m in nset.copy(): nset.add(m + n) return sums / 2 in nset

X. DP2
http://www.cnblogs.com/wangxiaobao/p/5943978.html

用01背包的思路，bool值 dp[i][j] 表示从0,1,2...i选重量为j是否可能。

则有递推关系：

dp[i][j] = dp[i - 1][j] || dp[i][j - nums[i]]; （i位置取或者不取）

结果返回值为dp[nums.size() - 1][sum]; （sum为和的一半）

 3     bool canPartition(vector<int>& nums) {
 4         int sum = 0;
 5         for (int i = 0; i < nums.size(); ++i) {
 6             sum += nums[i];
 7         }
 8         if (sum % 2 == 1) {
 9             return false;
10         } 
11         sum /= 2;
12         int dp[nums.size()][sum] = {false};
13         if (nums.size() == 1) {
14             return false;
15         }
16         for (int i = 0; i <= sum; ++i) {
17             if (nums[0] == i) {
18                 dp[0][i] = true;
19             }
20         }
21         for (int i = 1; i < nums.size(); ++i) {
22             for (int j = 1; j <= sum; ++j) {
23                 dp[i][j] = dp[i - 1][j] || dp[i][j - nums[i]];
24             }
25         }
26         return dp[nums.size() - 1][sum];
27     }

X. DFS+Cache - TLE
https://discuss.leetcode.com/topic/62267/java-solution-with-commets-using-dfs

    public boolean canPartition(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int sum = 0;
        for(int i : nums){
            if(map.containsKey(i)){
                map.put(i, map.get(i) + 1);
            }else{
                map.put(i, 1);
            }
            sum += i;
        }
        if(sum % 2 == 1) return false;
        return helper(map, sum / 2);
    }
    
    private boolean helper(Map<Integer, Integer> map, int target){
        /*target is achieveable*/
        if(map.containsKey(target) && map.get(target) > 0) return true;
        /*dfs*/
        for(int key : map.keySet()){
            if(key < target && map.get(key) > 0){
                map.put(key, map.get(key) - 1);
                if(helper(map, target - key)) return true;
                map.put(key, map.get(key) + 1);
            }
        }
        return false;
    }
}

https://discuss.leetcode.com/topic/62342/why-dp-is-slower-than-dfs-even-with-no-memoization/

The N in DFS is the length of the input array, while in DP it is the half of the summation of all elements in the input array. It might be possible that the length of the input array is short, however, the summation is pretty large, in which case DP performs worse than DFS.

Could be. But then again: both size and elements have the same bound in the problem description (100). That means the maximum possible sum is O(N^2). That makes DP O(N^3), and backtracking is still O(2^N). Even when N is around 20 they should be on about the same level, for larger N backtracking should be prohibitively slow! And there are test cases as large as 50 elements.

X. DFS - Brute Force
http://blog.csdn.net/mebiuw/article/details/52765840
老旧的暴力法 仅供参考 不可AC
/** * 首先和为奇数的过滤 * 其次使用DFS * 排序后可以剪枝很多情况 * */ public boolean canPartition(int[] nums) { Arrays.sort(nums); int sum=0; for (int num:nums) sum+= num; if(sum % 2 == 1) return false; sum/=2; return dfs(0,sum,nums); } // 一一尝试 public boolean dfs(int index,int sum,int[] nums){ sum -= nums[index] ; if(sum == 0) return true; for(int i=index+1;i<nums.length;i++){ if(sum<nums[i]) break; if(dfs(i,sum,nums)) return true; } return false; }
http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode416-partition-equal-subset-sum

X. BitSet
https://discuss.leetcode.com/topic/62334/simple-c-4-line-solution-using-a-bitset
the question description has changed (max array size 100 ==> 200). I have modified my code below according to the new description, and also made it a bit easier to understand.

Time complexity O(n), size of the bitset is 1256 bytes

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int MAX_NUM = 100;
        const int MAX_ARRAY_SIZE = 200;
        bitset<MAX_NUM * MAX_ARRAY_SIZE / 2 + 1> bits(1);
        int sum = 0;
        for (auto n : nums) {
            sum += n;
            bits |= bits << n;
        }
        return !(sum % 2) && bits[sum / 2];
    }
};

It's possible to shorten the solution to 4 lines, by using std::accumulate(), but that doesn't really make you type less or make it run faster though...

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> bits(1);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        for (auto n : nums) bits |= bits << n;
        return !(sum & 1) && bits[sum >> 1];
    }
};

http://www.cnblogs.com/grandyang/p/5951422.html
这道题还可以用bitset来做，感觉也十分的巧妙，bisets的大小设为5001，为啥呢，因为题目中说了数组的长度和每个数字的大小都不会超过100，那么最大的和为10000，那么一半就是5000，前面再加上个0，就是5001了。我们初始化把最低位赋值为1，然后我们算出数组之和，然后我们遍历数字，对于遍历到的数字num，我们把bits向左平移num位，然后再或上原来的bits，这样所有的可能出现的和位置上都为1。举个例子来说吧，比如对于数组[2,3]来说，初始化bits为1，然后对于数字2，bits变为101，我们可以看出来bits[2]标记为了1，然后遍历到3，bits变为了101101，我们看到bits[5],bits[3],bits[2]都分别为1了，正好代表了可能的和2，3，5，这样我们遍历玩整个数组后，去看bits[sum >> 1]是否为1即可

    bool canPartition(vector<int>& nums) {
        bitset<5001> bits(1);
        int sum = 0;
        for (auto n : nums) {
            sum += n;
            bits |= bits << n;
        }
        return !(sum & 1) && bits[sum >> 1]; // !(sum % 2) && bits[sum / 2];
    }

http://love-oriented.com/pack/P01.html
X. Related
Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks

Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.

http://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/

All the sums can be generated by either 
(1) including that element in set 1.
(2) without including that element in set 1.
So possible combinations are :-  
arr[0]   (1 or 2)  -> 2 values
arr[1]    (1 or 2)  -> 2 values
.
.
.
arr[n]     (2 or 2)  -> 2 values
So time complexity will be 2*2*..... *2 (For n times),
that is O(2^n)

int findMinRec(int arr[], int i, int sumCalculated, int sumTotal)

{

    // If we have reached last element.  Sum of one

    // subset is sumCalculated, sum of other subset is

    // sumTotal-sumCalculated.  Return absolute difference

    // of two sums.

    if (i==0)

        return abs((sumTotal-sumCalculated) - sumCalculated);

    // For every item arr[i], we have two choices

    // (1) We do not include it first set

    // (2) We include it in first set

    // We return minimum of two choices

    return min(findMinRec(arr, i-1, sumCalculated+arr[i-1], sumTotal),

               findMinRec(arr, i-1, sumCalculated, sumTotal));

}

// Returns minimum possible difference between sums

// of two subsets

int findMin(int arr[], int n)

{

    // Compute total sum of elements

    int sumTotal = 0;

    for (int i=0; i<n; i++)

        sumTotal += arr[i];

    // Compute result using recursive function

    return findMinRec(arr, n, 0, sumTotal);

}

// Returns the minimum value of the difference of the two sets.

int findMin(int arr[], int n)

{

    // Calculate sum of all elements

    int sum = 0;

    for (int i = 0; i < n; i++)

        sum += arr[i];

    // Create an array to store results of subproblems

    bool dp[n+1][sum+1];

    // Initialize first column as true. 0 sum is possible

    // with all elements.

    for (int i = 0; i <= n; i++)

        dp[i][0] = true;

    // Initialize top row, except dp[0][0], as false. With

    // 0 elements, no other sum except 0 is possible

    for (int i = 1; i <= sum; i++)

        dp[0][i] = false;

    // Fill the partition table in bottom up manner

    for (int i=1; i<=n; i++)

    {

        for (int j=1; j<=sum; j++)

        {

            // If i'th element is excluded

            dp[i][j] = dp[i-1][j];

            // If i'th element is included

            if (arr[i-1] <= j)

                dp[i][j] |= dp[i-1][j-arr[i-1]];

        }

    }

  

    // Initialize difference of two sums.

    int diff = INT_MAX;

     

    // Find the largest j such that dp[n][j]

    // is true where j loops from sum/2 t0 0

    for (int j=sum/2; j>=0; j--)

    {

        // Find the

        if (dp[n][j] == true)

        {

            diff = sum-2*j;

            break;

        }

    }

    return diff;

}