# 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)
