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%