698. Partition to K Equal Sum Subsets
Đề Bài
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 <= 161 <= nums[i] <= 104- The frequency of each element is in the range
[1, 4].
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n log n)
💾 Không gian
O(n)
Lời Giải
Python
0698-partition-to-k-equal-sum-subsets.py
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
n = len(nums)
total = sum(nums)
if total % k != 0 or n < k:
return False
d = total // k
flags = [0] * k
nums.sort(reverse = True)
def backTracking(i):
if i == n:
return True
seen = set()
for j in range(k):
if flags[j] in seen:
continue
if flags[j] + nums[i] <= d:
seen.add(flags[j])
flags[j] += nums[i]
if backTracking(i + 1):
return True
flags[j] -= nums[i]
return False
return backTracking(0)