## Tuesday, May 8, 2018

### LeetCode 698 - Partition to K Equal Sum Subsets

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

• X. DFS
As even when k = 2, the problem is a "Subset Sum" problem which is known to be NP-hard, (and because the given input limits are low,) our solution will focus on exhaustive search.
A natural approach is to simulate the k groups (disjoint subsets of nums). For each number in nums, we'll check whether putting it in the i-th group solves the problem. We can check those possibilities by recursively searching.
Firstly, we know that each of the k group-sums must be equal to target = sum(nums) / k. (If this quantity is not an integer, the task is impossible.)
For each number in nums, we could add it into one of k group-sums, as long as the group's sum would not exceed the target. For each of these choices, we recursively search with one less number to consider in nums. If we placed every number successfully, then our search was successful.
One important speedup is that we can ensure all the 0 values of each group occur at the end of the array groups, by enforcing if (groups[i] == 0) break;. This greatly reduces repeated work - for example, in the first run of search, we will make only 1 recursive call, instead of k. Actually, we could do better by skipping any repeated values of groups[i], but it isn't necessary.
Another speedup is we could sort the array nums, so that we try to place the largest elements first. When the answer is true and involves subsets with a low size, this method of placing elements will consider these lower size subsets sooner. We can also handle elements nums[i] >= target appropriately. These tricks are not necessary to solve the problem, but they are presented in the solutions below.

• Time Complexity: $O(k^{N-k} k!)$, where $N$ is the length of nums, and $k$ is as given. As we skip additional zeroes in groups, naively we will make $O(k!)$ calls to search, then an additional $O(k^{N-k})$ calls after every element of groups is nonzero.
• Space Complexity: $O(N)$, the space used by recursive calls to search in our call stack.
    public boolean search(int[] groups, int row, int[] nums, int target) {
if (row < 0) return true;
int v = nums[row--];
for (int i = 0; i < groups.length; i++) {
if (groups[i] + v <= target) {
groups[i] += v;
if (search(groups, row, nums, target)) return true;
groups[i] -= v;
}
if (groups[i] == 0) break;
}
return false;
}

public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k > 0) return false;
int target = sum / k;

Arrays.sort(nums);
int row = nums.length - 1;
if (nums[row] > target) return false;
while (row >= 0 && nums[row] == target) {
row--;
k--;
}
return search(new int[k], row, nums, target);
}
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/JavaC++Straightforward-dfs-solution
Assume sum is the sum of nums[] . The dfs process is to find a subset of nums[] which sum equals to sum/k. We use an array visited[] to record which element in nums[] is used. Each time when we get a cur_sum = sum/k, we will start from position 0 in nums[] to look up the elements that are not used yet and find another cur_sum = sum/k.
An corner case is when sum = 0, my method is to use cur_num to record the number of elements in the current subset. Only if cur_sum = sum/k && cur_num >0, we can start another look up process.
Some test cases may need to be added in:
nums = {-1,1,0,0}, k = 4
nums = {-1,1}, k = 1
nums = {-1,1}, k = 2
nums = {-1,1,0}, k = 2
    public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num:nums)sum += num;
if(k <= 0 || sum%k != 0)return false;
int[] visited = new int[nums.length];
return canPartition(nums, visited, 0, k, 0, 0, sum/k);
}

public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
if(k==1)return true;
if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
for(int i = start_index; i<nums.length; i++){
if(visited[i] == 0){
visited[i] = 1;
if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
visited[i] = 0;
}
}
return false;
}

 We don't need to track number of elements 

 bool canPartitionKSubsets(vector<int>& nums, int k) { int S = 0; int n = nums.size(); for (int e:nums) S += e; if (S%k != 0) return false; S = S/k; vector<bool> visited(n, false); return canPartition(nums,visited, k, 0, 0, S); } bool canPartition(vector<int>& nums, vector<bool>& visited, int k, int start, int s, int S) { if (k == 1) return true; if (s == S) return canPartition(nums, visited, k-1, 0, 0, S); for (int i = start; i < nums.size(); i++) { if (!visited[i]) { visited[i] = true; if (canPartition(nums,visited, k, i+1, s+nums[i], S)) return true; visited[i] = false; } } return false; } 

As in Approach #1, we investigate methods of exhaustive search, and find target = sum(nums) / k in the same way.
Let used have the i-th bit set if and only if nums[i] has already been used. Our goal is to use nums in some order so that placing them into groups in that order will be valid. search(used, ...) will answer the question: can we partition unused elements of nums[i] appropriately?
This will depend on todo, the sum of the remaining unused elements, not crossing multiples of target within one number. If for example our target is 10, and our elements to be placed in order are [6, 5, 5, 4], this would not work as 6 + 5 "crosses" 10 prematurely.
If we could choose the order, then after placing 5, our unused elements are [4, 5, 6]. Using 6 would make todo go from 15 to 9, which crosses 10 - something unwanted. However, we could use 5 since todogoes from 15 to 10; then later we could use 4 and 6 as those placements do not cross.
It turns out the maximum value that can be chosen so as to not cross a multiple of target, is targ = (todo - 1) % target + 1. This is essentially todo % target, plus target if that would be zero.
Now for each unused number that doesn't cross, we'll search on that state, and we'll return true if any of those searches are true.
Notice that the state todo depends only on the state used, so when memoizing our search, we only need to make lookups by used.
In the solutions below, we present both a top-down dynamic programming solution, and a bottom-up one. The bottom-up solution uses a different notion of state.

enum Result { TRUE, FALSE }

boolean search(int used, int todo, Result[] memo, int[] nums, int target) {
if (memo[used] == null) {
memo[used] = Result.FALSE;
int targ = (todo - 1) % target + 1;
for (int i = 0; i < nums.length; i++) {
if ((((used >> i) & 1) == 0) && nums[i] <= targ) {
if (search(used | (1<<i), todo - nums[i], memo, nums, target)) {
memo[used] = Result.TRUE;
break;
}
}
}
}
return memo[used] == Result.TRUE;
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k > 0) return false;

Result[] memo = new Result[1 << nums.length];
memo[(1 << nums.length) - 1] = Result.TRUE;
return search(0, sum, memo, nums, sum / k);
}


Bottom-Up Variation

    public boolean canPartitionKSubsets(int[] nums, int k) {
int N = nums.length;
Arrays.sort(nums);
int sum = Arrays.stream(nums).sum();
int target = sum / k;
if (sum % k > 0 || nums[N - 1] > target) return false;

boolean[] dp = new boolean[1 << N];
dp[0] = true;
int[] total = new int[1 << N];

for (int state = 0; state < (1 << N); state++) {
if (!dp[state]) continue;
for (int i = 0; i < N; i++) {
int future = state | (1 << i);
if (state != future && !dp[future]) {
if (nums[i] <= target - (total[state] % target)) {
dp[future] = true;
total[future] = total[state] + nums[i];
} else {
break;
}
}
}
}
return dp[(1 << N) - 1];
}

• Time Complexity: $O(N * 2^N)$, where $N$ is the length of nums. There are $2^N$ states of used (or statein our bottom-up variant), and each state performs O(N) work searching through nums.
• Space Complexity: $O(2^N)$, the space used by memo (or dptotal in our bottom-up variant).