Участник:Hellhoundmipt/partition-to-k-equal-sum-subsets/submissions

Материал из DISCOPAL
< Участник:Hellhoundmipt
Версия от 09:25, 7 декабря 2020; Hellhoundmipt (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/partition-to-k-equal-sum-subsets/submissions/ Scala код <code-cpp> object Solution { def canPartitionKSubsets(nums: Array[I…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/submissions/

Scala код

object Solution {
    def canPartitionKSubsets(nums: Array[Int], k: Int): Boolean = {
        val sum = nums.sum
        val max = nums.max
        val targetSubsetSum = sum / k
        if (sum % k != 0 || max > sum / k) return false
        recursion(nums, k, Array.fill(nums.length)(false), targetSubsetSum, 0, 0)
    }
 
    def recursion(nums: Array[Int], k: Int, visited: Array[Boolean], targetSubsetSum: Int, subsetSum: Int, nextInd: Int): Boolean = {
        if (k == 0) return true
        if (subsetSum == targetSubsetSum) return recursion(nums, k - 1, visited, targetSubsetSum, 0, 0)
        for (i <- nextInd until nums.length) {
            if (!visited(i) && subsetSum + nums(i) <= targetSubsetSum) {
                visited(i) = true
                if (recursion(nums, k, visited, targetSubsetSum, subsetSum + nums(i), i + 1)) return true
                visited(i) = false
            }
        }
        false
    }
 
}