LeetCode 698 Partition to K Equal Sum Subsets

LeetCode 698 Partition to K Equal Sum Subsets

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.

题目大意：

判断数组nums是否可以划分为k个和相等的子数组

解题思路：

这题与416类似，所以一开始考虑用0-1背包问题思路，但是0-1背包问题得出的解为2,2,1，与答案不同。因为背包问题只能求出第一个解，并不能求出k个解。所以类似于排列组合，
需要DFS来一个个数来试。参数为visited数组为记录该数是否用了，curSum，k，若curSum等于target(sum/k)，找到第一个解，k–，curSum=0，找下一个解。这个方法是用k次排列组合法组成最终解。

注意事项：

1. 数组和为不能被k整除，无解
2. 引入st，排列组合必须，用于for循环的起始点。
3. k=1立刻剪枝，因为前三个解都是等于sum/k,最后一个也一定是sum/k
4. 当curSum==target时，进行k-1，curSum=0的下一轮dfs。

Java代码：

public boolean canPartitionKSubsets0(int[] nums, int k) {
	int sum = 0;
	for(int i : nums)
		sum+=i;
	if(sum%k!=0)
		return false;
	boolean[] visited = new boolean[nums.length];
	return dfs0(nums, k, sum/k, 0, visited, 0);
}

public boolean dfs0(int[] nums, int k, int target, int curSum, boolean[] visited, int start){
	if(k==1)
		return true;
	if(curSum==target)
		return dfs0(nums, k-1, target, 0, visited, 0);
	
	for(int i=start;i<nums.length;i++){
		if(visited[i])
			continue;
		if(curSum+nums[i]<=target){
			visited[i] = true;
			if(dfs0(nums, k, target, curSum+nums[i], visited, i+1))
				return true;
			visited[i] = false;
		}
	}
	return false;
}

算法分析：

这是NP问题。

---

另一个方法是，将k次排列组合法整合成一次，途径是开一个k大小数组，每一个数肯定属于其中一个。visited数组替换成ksum数组和idx控制遍历数组顺序。某一个数肯定是属于ksum数组的任一个，
所以所有可能性都考虑到，可以求得解。先对原数组排序方便从后往前遍历，贪心算法可以帮助剪枝，因为先填大的数，容易获得结果或排除结果。如[1….1, 4], target=4, k=2，从前往后的话，
多个1可以有非常多的可能。提高算法效率但若不排序的话会得到LTE。
这个方法比第一个方法的优势在于它用ksum数组取代visited和curSum参数，第一种方法要从头开始扫k遍数组，而此法只需扫一遍数组+每个元素试k次。

1. 数组和为不能被k整除，无解
2. 对数组排序
3. DFS四部曲，从后往前遍历数组加入ksum

注意事项：

1. 数组和为不能被k整除，无解
2. 从后往前遍历数组

Java代码：

public boolean canPartitionKSubsets(int[] nums, int k) {
	int sum = 0;
	for(int i : nums)
		sum+=i;
	if(sum%k!=0)
		return false;
	Arrays.sort(nums);
	int[] ksum = new int[k];
	return dfs(nums, k, sum/k, ksum, nums.length-1);
}

public boolean dfs(int[] nums, int k, int target, int[] ksum, int idx){
	if(idx==-1){
		for(int a : ksum)
			if(a!=target)
				return false;
		return true;
	}
	for(int i=0; i<k; i++){
		if(ksum[i]+nums[idx]<=target){
			ksum[i] += nums[idx];
			if(dfs(nums, k, target, ksum, idx-1))
				return true;
			ksum[i] -= nums[idx];
		}
		
	}
	return false;
}

算法分析：

这是NP问题。