# Leetcode - Partition to K Equal Sum Subsets

violet posted @ May 29, 2020 06:41:44 AM in 算法 with tags Algorithm DFS Golang , 318 阅读

https://leetcode.com/problems/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:

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

```func canPartitionKSubsets(nums []int, k int) bool {
sum := 0
for _, n := range nums {
sum += n
}
if sum % k != 0 {
return false
}

visited := make([]bool, len(nums))

return canPartition(nums, &visited, 0, k, 0, 0, sum/k)
}

func canPartition(nums []int, visited *[]bool, start, k, curSum, curNum, target int) bool {
if k == 1 {
return true
}
if curSum == target && curNum > 0 {
return canPartition(nums, visited, 0, k-1, 0, 0, target)
}

for i := start; i < len(nums); i++ {
if !(*visited)[i] {
(*visited)[i] = true
if canPartition(nums, visited, i+1, k, curSum + nums[i], curNum+1, target) {
return true
}
(*visited)[i] = false
}
}
return false
}```

time complexity: O(2^n)

Escorts in Domlur 说:
Dec 21, 2021 06:01:25 PM

The criteria for this is quite nice we always try to learn from our mistakes.

Escorts in Domlur 说:
Dec 21, 2021 06:03:35 PM

Awesomeness is there in the topic as quality is present in the topic.

HMWSSB Water Bill 说:
Dec 20, 2022 11:11:33 PM

In Telangana state, we have different taxes and billing systems that every citizen has to follow, and for Hyderabad, the Water bill is a necessity that is billed every month to all individuals who have a water connection. HMWSSB Water Bill The Hyderabad Metropolitan Water Supply & Sewerage Board is responsible for managing the water amenity in Hyderabad along with the water bill management. So, if you have a water connection then you have to pay your GHMC Water Bill every month.

(输入验证码)
or Ctrl+Enter