Description

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.

Constraints

• \(1 \le k \le nums.length \le 16\)
• \(1 \le nums_i \le 10^4\)
• The frequency of each element is in the range \([1, 4]\)

Solution

状压可达性DP

Code

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long sum = 0;
        for(auto v : nums) sum += v;
        if(sum % k) return false;
        long d = sum / k;
        auto dfs = [&nums, d, dp = vector<char>(1<<nums.size(), 1)]
                    (auto &&f, int S, int sum) mutable -> bool {
            if(!S) return true;
            if(!dp[S]) return false;
            for(int i = 0; i < nums.size(); ++i) {
                if(nums[i] + sum > d) break;
                if(S >> i & 1) {
                    int v = nums[i] + sum;
                    if(v == d) v = 0;
                    if(f(f, S ^ (1<<i), v)) {
                        return true;
                    }
                }
            }
            return dp[S] = false;
        };
        return dfs(dfs, (1<<nums.size())-1, 0);;
    }
};

Link

LeetCode-698 Partition to K Equal Sum Subsets