698. Partition to K Equal Sum Subsets

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

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.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Constraints:

• 1 <= k <= nums.length <= 16
• $1<=nums[i]<={10}^4$
• The frequency of each element is in the range [1, 4].

Code

class Solution {
    public boolean canPartitionKSubsets(int[] arr, int k) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) sum += arr[i];

        if (sum % k != 0) return false;

        return helper(arr, 0, k, sum / k, 0, new HashSet<>());
    }

    private boolean helper(
        int[] arr,
        int curr,
        int k,
        int target,
        int currSelectedMask,
        HashSet<Integer> selectedMask
    ) {
        if (k == 1) return true;
        if (curr > target) return false;

        if (selectedMask.contains(currSelectedMask)) {
            return false;
        }

        if (curr == target) {
            boolean res = helper(arr, 0, k - 1, target, currSelectedMask, selectedMask);
            selectedMask.add(currSelectedMask);
            return res;
        }

        for (int i = 0; i < arr.length; i++) {
            // 还没选过
            if ((currSelectedMask & (1 << i)) == 0) {
                currSelectedMask |= 1 << i;

                if (helper(arr, curr + arr[i], k, target, currSelectedMask, selectedMask)) {
                    return true;
                }
                // 把这一位重新置0 相当于取消选择
                currSelectedMask ^= 1 << i;
            }
        }

        selectedMask.add(currSelectedMask);
        return false;
    }
}

• Time complexity: $O(N\ast 2^N)$
• Space complexity: $O(2^N)$