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.

看code吧，不是很会写，时间复杂度这个题所有解法都是指数型的 很高

Loading...LeetCode

class Solution {

   private int subSum;
    private int k;
    private boolean[] used;
    private int[] nums;
	public boolean canPartitionKSubsets(int[] nums, int k) {
		int sum = 0;
        
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % k != 0)
            return false;
        
        
        this.subSum = sum / k;
        
        this.k = k;
        
        this.used = new boolean[nums.length];
        this.nums = nums;
        int index = 0;
        
        return dfs(0,0, 0);
        
	}
    
    public boolean dfs(int index, int sum,int matched){
        if(subSum == sum){
            return matched + 1 == k || dfs(0,0,matched+1);
        }
        
        else if(sum > subSum){
            return false;
        }
        else {
            
            if(index == nums.length){
                return false;
            }
            boolean flag = false;
            if(!used[index]){
                used[index] = true;
                flag = dfs(index+1,sum+nums[index],matched);
                used[index] = false;
            }
            
            return flag || dfs(index+1, sum, matched);
        }
    }

	
}

1. 时间复杂度：O(k ^ N)，其中N时nums的长度，k是子集数。如果采用了优化方案a，则复杂度至少降到O(k ^ (N - k) * k!)，因为一开始会跳过很多和为0的子集，至少前k个元素的搜索次数不超过O(k!)。

2. 空间复杂度：O(N)， 用于函数调用栈。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        
        for(int x : nums){
            sum += x;
        }
        
        if(sum % k != 0){
            return false;
        }
        
        int subSum = sum / k;
        
        Arrays.sort(nums);
        
        int beginIndex = nums.length-1;
        
        if(nums[beginIndex] > subSum){
            return false;
        }
        
        while(beginIndex >= 0&& nums[beginIndex] == subSum){
            beginIndex--;
            k--;
        }
        
        return partition(new int[k], nums,beginIndex, subSum);
    }
    
    public boolean partition(int[] subsets, int[] nums, int index, int target){
        if(index < 0){
            return true;
        }
        
        int selected = nums[index];
        
        for(int i = 0; i < subsets.length;i++){
            if(subsets[i] + selected <= target){
                subsets[i] += selected;
                if(partition(subsets,nums,index - 1, target)){
                    return true;
                }
                
                subsets[i] -= selected;
            }
        }
        
        return false;
    }
}