# 698. Partition to K Equal Sum Subsets

refer this!

<https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247490981&idx=1&sn=db17864d2f6f189d63e051e434c05460&scene=21#wechat_redirect>

## 經典題目

## from bucket view

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FFj5eV1fJgHaoyEt19hVg%2Fimage.png?alt=media\&token=1273c9e0-ecfa-4ad8-bc4f-314220f37791)

T: O(k\*2^n)

S: O(n)

We have used an extra array of size N to mark the already used elements.&#x20;

And the recursive tree makes at most N calls at one time, so the recursive stack also takes O(N) space

```java
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        Arrays.sort(nums); // prunin
        reverse(nums);
        return dfs(k, nums, 0, 0, new boolean[16], sum/k);
    }
    
    private boolean dfs(int k, int[] nums, int start, int sum, boolean[] visited, int mean) {
        if (k == 0) {
            return true;
        }
        // 換下個 group, set start = 0, sum = 0
        // 為什麼可以設 start 從 0 開始跑呢, 因為有紀錄 visited, 所以使用過的, 會跳過, 所以從 0 開始
        // sum = 0 很直觀, 因為要來計算下個 group 的和到 mean 了沒 
        if (sum == mean) {
            return dfs(k-1, nums, 0, 0, visited, mean);
        }
        
        int last = -1;
        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (sum + nums[i] > mean) { // pruning
                continue;
            }
            if (nums[i] == last) { // pruning : skip same number
                continue;
            }
            visited[i] = true;
            sum += nums[i];
            
            last = nums[i]; 
            if (dfs(k, nums, start + 1, sum, visited, mean)) {
                return true;
            }
            
            sum -= nums[i];
            visited[i] = false;
        }
        return false;
    }
    private void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
```

## from numbers view

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FsqF9VGJHdepAEM9Kyanq%2Fimage.png?alt=media\&token=c5f0d8f2-c313-460b-b2a9-04881858ec45)

T: O(k^n), with pruning beats 92%

S: O(n)

```java
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int m : nums) {
            sum += m;
        }
        if (sum % k != 0) {
            return false;
        }
        Arrays.sort(nums); // prune 0
        reverse(nums);
        return dfs(nums, new int[k], 0, sum/k);
    }
    
    private boolean dfs(int[] matchsticks, int[] buckets, int start, int target) {
        if (start == matchsticks.length) {
            return true;
        }
        
        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i-1] == buckets[i]) { // prune 1, 這個 prune 差超多的
                continue;
            }
            if (buckets[i] + matchsticks[start] > target) { // prune 2
                continue;
            }
            buckets[i] += matchsticks[start];
            if (dfs(matchsticks, buckets, start+1, target)) {
                return true;
            }
            buckets[i] -= matchsticks[start];
        }
        return false;
    }
    private void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}


```


---

# 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://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips/dispatch-to-k-subsets-or-subsets/698.-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.