# 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:**<br>

```
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吧，不是很会写，时间复杂度这个题所有解法都是指数型的 很高

{% embed url="<https://leetcode.com/articles/partition-to-k-equal-sum-subsets/>" %}

```java
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)， 用于函数调用栈。

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shuati.gitbook.io/crack-lintcode/linkedin/partition-to-k-equal-sum-subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.