Given an integer array nums and an integer k, return true if it is 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 is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2:
Input: nums = [1,2,3,4], k = 3
Output: false
Constraints:
1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].
题意：
给定一个数组，和k值
把数组拆分成k个数组，每个数组的sum值相等。
总的sum值可以计算出来，k也是知道的，所以单个数组的sum值也是知道的。所以也就是求收否可以才分成k个数组，每个数组都等于sum(one slice).已知
这种往数组中填值的题目一般都是使用回溯法
回溯法：
回溯函数的入参是数组和index，空值可选集合。
还有当前sum值cur，以及目标sum值target
每一层遍历可选集合，只要cur+nums[i] 小于等于target的就可以走向下一层。
回溯出口：index>len(nums) 表示有解，走到了最深处。
剪枝优化：对于某一层回溯函数而言，如果选择了nums[i]无解，那么当选择nums[i+1]时，就不需要再考虑nums[i]了。
需要需要设置一个cache，存储nums[i]，当满足一个子数组时往下层走则清空。
func canPartitionKSubsets(nums []int, k int) bool {
sum, max := 0, 0
for _, num := range nums {
if num > max {
max = num
}
sum += num
}
n := sum / k
if n*k != sum || max > n {
return false
}
return backTrack(nums, 0, 0, n, make(map[int]bool, len(nums)))
}
func backTrack(nums []int, index int, cur, target int, cache map[int]bool) bool {
if index >= len(nums) {
return true
}
if cur == target {
cur = 0
}
for i := index; i < len(nums); i++ {
if cache[nums[i]] {
continue
}
temp := cur + nums[i]
if temp <= target {
nums[i], nums[index] = nums[index], nums[i]
res := false
if temp == target {
res = backTrack(nums, index+1, temp, target, make(map[int]bool))
} else {
mp := make(map[int]bool, len(cache))
for k := range cache {
mp[k] = true
}
res = backTrack(nums, index+1, temp, target, mp)
}
if res {
return true
}
nums[index], nums[i] = nums[i], nums[index]
}
cache[nums[i]] = true
}
return false
}