# Partition to K Equal Sum Subsets

<https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/>

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

## Thoughts

能否问把数组分成K份，使得它们的和都一样。分成两份可以直接背包DP，分成K写递推就很麻烦。用DFS搜索所有的可能的subset的和等于sum，满足一个就让K -1。当K == 1时说明已经找到了K -1个sum相等的subset，最后一个subset不用算肯定也是和为sum。

## Code

```cpp
/*
 * @lc app=leetcode id=698 lang=cpp
 *
 * [698] Partition to K Equal Sum Subsets
 *
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
 *
 * algorithms
 * Medium (43.32%)
 * Likes:    1007
 * Dislikes: 57
 * Total Accepted:    53.2K
 * Total Submissions: 122.2K
 * Testcase Example:  '[4,3,2,3,5,2,1]\n4'
 *
 * 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.
 * 
 * 
 */
class Solution {
public:
    bool dfs(vector<int> &nums, int pos, int sum, vector<bool> &visited, const int K, const int T) {
        // 前面K - 1份都满足，最后一份一定也是
        if (K == 1) return true;
        if (sum == 0) return dfs(nums, 0, T, visited, K - 1, T);
        for (int i = pos; i < nums.size(); ++i) {
            if (!visited[i] && (sum - nums[i] >= 0)) {
                visited[i] = true;
                if (dfs(nums, i + 1, sum - nums[i], visited, K, T)) return true;
                visited[i] = false;
            }
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        vector<bool> visited(nums.size());
        return dfs(nums, 0, sum / k, visited, k, sum / k);
    }
};


```

## Ver.2

为了避免访问过(4,3)再到3时访问(3, 4)的情况，我们可以引入一个startIndex, 表示这次应该从哪开始，并且下次递归在target != 0时只能从index > startIndex里选，这样就避免了(3, 2, 1)的出现，相当于我们对subset内部固定一种顺序(combination)，而subset之间继续permutation。

```
class Solution {
    private boolean helper(int[] nums, int left, boolean[] visited, int curSize, int t, int start) { 
        if (left == 0) {  
            if (curSize == nums.length) {
                return true;
            } else {
                left = t;
                return helper(nums, t, visited, curSize, t, 0);
            }
        }

        for (int i = start; i < nums.length; i++) {
            if (!visited[i] && left - nums[i] >= 0) {
                visited[i] = true;
                if (helper(nums, left - nums[i], visited, curSize + 1, t, start + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }

        return false;
    }

    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;
        }
        boolean[] visited = new boolean[nums.length];

        return helper(nums, sum / k, visited, 0, sum / k, 0);
    }
}
```

## Ver. 3

把更新curSize替换成更新k能让速度更快。我们每次找到一个满足和为t的subset，即相当于把k - 1. 这样我们能减少检查一个subset的时间。

```
class Solution {
    private boolean helper(int[] nums, int index, int left, boolean[] visited, int k, int t) {
        if (k == 1) {
            return true;
        }
        if (left == 0) {  
            return helper(nums, 0, t, visited, k - 1, t);
        }   

        for (int i = index; i < nums.length; i++) {
            if (!visited[i] && left - nums[i] >= 0) {
                visited[i] = true;
                if (helper(nums, i + 1, left - nums[i], visited, k, t)) {
                    return true;
                }
                visited[i] = false;
            }
        }

        return false;
    }

    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;
        }
        boolean[] visited = new boolean[nums.length];

        return helper(nums, 0, sum / k, visited, k, sum / k);
    }
}
```


---

# 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://hao-fu-1.gitbook.io/oj/exhaustive-search/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.