## Sunday, October 9, 2016

### LeetCode 416 - Partition Equal Subset Sum

Partition a set into two subsets such that the difference of subset sums is minimum - GeeksforGeeks

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
http://www.cnblogs.com/grandyang/p/5951422.html

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.
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/67539/0-1-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]]
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 Problem`which 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];
}``````

```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

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

``` 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

/** * 首先和为奇数的过滤 * 其次使用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

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