698. Partition to K Equal Sum Subsets

698. Partition to K Equal Sum Subsets

题目描述

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:

1
2
3
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.

题目大意

将数组平均分成 k 个子序列,每个子序列和相同。

解题思路

递归遍历数组,用 visited 标记访问过的元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
func canPartitionKSubsets(_ nums: [Int], _ k: Int) -> Bool {
let sum = nums.reduce(0, +)
var visted = Array(repeating: false, count: nums.count)
guard nums.count > k, sum % k == 0 else { return false }
let target = sum / k
func divide(k: Int, currentSum: Int, currentNum: Int, start: Int) -> Bool {
if k == 1 { return true }
if currentSum == target && currentNum > 0 {
return divide(k: k - 1, currentSum: 0, currentNum: 0, start: 0)
}
for i in start..<nums.count {
if !visted[i] {
if nums[i] + currentSum > target { continue }
visted[i] = true
if divide(k: k, currentSum: currentSum + nums[i], currentNum: currentNum + 1, start: i + 1) {
return true
}
visted[i] = false
}
}
return false
}
return divide(k: k, currentSum: 0, currentNum: 0, start: 0)
}
}
0%