文章目錄

• 1 理解題目
• 2 分析
• 2.1進一步優(yōu)化
• 2.2 根據(jù)花花醬解答

1 理解題目

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.
輸入：一個int數(shù)組nums，一個int k
規(guī)則：將nums分成k個子數(shù)組，每個子數(shù)組的和相等
輸出：true：如果可以將nums分成k個和相等的子數(shù)組。否則false。

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.

2 分析

nums能分成k份，每一份的和應(yīng)該是總和/k。那就首先確認：總和%k=0。
每一個子數(shù)組的和應(yīng)該是:target=總和/k。如果某個元素的值>target，那也是不可分的。每個元素至少有一個元素，比target大的元素單獨成一個子數(shù)組，不符合和為target的要求。

現(xiàn)在就該想怎么把這些元素分到k個子數(shù)組中。
最開始映入我腦中的是雙指針。將nums排序，一個指針從左開始，一個指針從右開始。后來一想，子數(shù)組中的元素不一定是2個，被例題束縛了思維。那就不能這樣做。但數(shù)組排序應(yīng)該對。至于為什么，還不清楚。

那就嘗試用枚舉的方法。參考力扣官網(wǎng)。
將第0個元素1，可以放在第0個子數(shù)組中、第1個子數(shù)組、第2個子數(shù)組、第3個子數(shù)組。
將第1個元素2，嘗試放入第0,1,2,3個子數(shù)組，只要放入之后的和不超過target即可。
…
一直放到最后一個元素，將所有數(shù)字都放入了子數(shù)組中。

這里放入的過程不是直接將元素放進去，而是放入的是元素的和。

一個重要的細節(jié)是，通過判斷 if (groups[i] == 0) break;這是因為在嘗試了各種可能之后，groups[i]沒有合適的選項，所以直接返回false；

class Solution {private int[] nums;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);if(nums[nums.length-1]>target) return false;this.nums = nums;int[] groups = new int[k];return dfs(groups,0,target);}private boolean dfs(int[] group, int index, int target){if(index>=nums.length) return true;int v = nums[index++];for(int i=0;i<group.length;i++){if(group[i] + v<=target){group[i] += v;if(dfs(group,index,target)) return true;group[i] -= v;}if(group[i] == 0) break;}return false;} }

2.1進一步優(yōu)化

優(yōu)化的第一個地方是將數(shù)組末尾直接等于target的刪除。這個步驟優(yōu)化效果不明顯。
優(yōu)化的第二個地方是遍歷nums從最大值開始遍歷。自己可以手寫一下[1,2,2,3,3,4,5]這個例子，從大到小，與從小到大的枚舉情況，可以發(fā)現(xiàn)從大到小，可以很快找到答案。

class Solution {private int[] nums;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);if(nums[nums.length-1]>target) return false;this.nums = nums;int index = nums.length-1;while(index>=0 && nums[index]==target){index--;k--;}int[] groups = new int[k];return dfs(groups,index,target);}private boolean dfs(int[] group, int index, int target){if(index<0) return true;int v = nums[index--];for(int i=0;i<group.length;i++){if(group[i] + v<=target){group[i] += v;if(dfs(group,index,target)) return true;group[i] -= v;}if(group[i] == 0) break;}return false;} }

時間復(fù)雜度$O(k^{N?k}k!)$,N是nums的長度。

2.2 根據(jù)花花醬解答

c++代碼可以過，java代碼超時。來源地址。

class Solution {private int[] nums;public boolean canPartitionKSubsets(int[] nums, int k) {int sum = Arrays.stream(nums).sum();if(sum%k!=0) return false;int target = sum/k;if(nums[nums.length-1]>target) return false;Arrays.sort(nums);this.nums = nums;return dfs(0,0,k,target);}private boolean dfs(int current,int used,int k,int target){if(k==0) return (used == (1<<nums.length)-1);for(int i=0;i<nums.length;i++){if((used & (1<<i))>0) continue;int t = current + nums[i];if(t>target) break;int newUsed = (used | (1<<i));if(t==target){if(dfs(0,newUsed,k-1,target)) return true;}else{if(dfs(t,newUsed,k,target)) return true;}}return false;}}

總結(jié)

以上是生活随笔為你收集整理的698. Partition to K Equal Sum Subsets的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。