# 698     Partition to K Equal Sum Subsets

## 698. [Partition to K Equal Sum Subsets](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/)

## 1. Question

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`.

## 2. Implementation

**(1) Backtracking**

思路:

(1) 要将nums数组分成k个和相等的subset，第一步当然是求nums中的数的和sum，如果sum能被k除不为0，则这个nums不可能分成k个和相等的subset

(2)接下来就是通过递归方式求出是否存在k个和相等的subset，这里用两个base case:

a. 当group为1时，说明剩下的数可以组成一个subset，这时直接返回true

b. 当curSum等于target时，我们找到一个符合条件的group, 下一步就是从数组的开头重头开始搜索符合的条件的下一个group

```java
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || nums.length <= k) {
            return false;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % k != 0) {
            return false;
        }

        boolean[] used = new boolean[nums.length];
        return canPartitionKSubsets(nums, k, sum / k, 0, 0, used);
    }

    public boolean canPartitionKSubsets(int[] nums, int group, int target, int start, int curSum, boolean[] used) {
        // Only one group left, we can use the remaining numbers to form the subset
        if (group == 1) {
            return true;
        }

        // If current sum equals to target, we find a subset, restart the search from the beginning of nums to find the 
        // next valid subset
        if (curSum == target) {
            return canPartitionKSubsets(nums, group - 1, target, 0, 0, used);
        }

        for (int i = start; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                if (canPartitionKSubsets(nums, group, target, i + 1, curSum + nums[i], used)) {
                    return true;
                }
                used[i] = false;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(2^n), 最坏情况是搜索所有可能的subset，总共有2^n个，空间复杂度O(n)


---

# 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://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/698-partition-tok-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.