Leetcode - Partition to K Equal Sum Subsets

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)

• 相关文章
• 全局相关文章