698. 划分为 k 个相等的子集

题目描述

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

示例 2:

输入: nums = [1,2,3,4], k = 3
输出: false

提示：

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

解法一：状态压缩 + 记忆化搜索

 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
29
30
31
32
33
34
35
36
37
38
39


func canPartitionKSubsets(nums []int, k int) bool {
    n, sum := len(nums), 0
    for _, num := range nums {
        sum += num
    }
    if sum%k > 0 {
        return false
    }
    per := sum / k
    sort.Ints(nums)
    if nums[n-1] > per {
        return false
    }

    visited := make([]bool, 1<<n)
    var dfs func(s, p int) bool
    dfs = func(s, p int) bool {
        if s == 0 {
            if p != 0 {
                panic("error")
            }
            return true
        }
        if visited[s] {
            return false
        }
        visited[s] = true
        for i := 0; i < n; i++ {
            if nums[i]+p > per {
                break
            }
            if (s>>i)&1 > 0 && dfs(s^(1<<i), (p+nums[i])%per) {
                return true
            }
        }
        return false
    }
    return dfs((1<<n)-1, 0)
}