Daily LeetCode – day0053 0698. Partition to K Equal Sum Subsets

import java.util.HashMap;
import java.util.Map;

// 0698. Partition to K Equal Sum Subsets
class Solution {
    Map<Integer, Boolean> hashMap = new HashMap<>();

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) return false;
        return backtrack(nums, 0, 0, k, 0, sum / k);
    }

    private boolean backtrack(int[] nums, int start, int bucket, int k, int used, int target) {
        if (k == 0) return true;
        if (bucket == target) {
            boolean res = backtrack(nums, 0, 0, k - 1, used, target);
            hashMap.put(used, res);
            return res;
        }
        if (hashMap.containsKey(used)) {
            return hashMap.get(used);
        }
        for (int i = start; i < nums.length; ++i) {
            if (((used >> i) & 1) == 1) continue;
            if (bucket + nums[i] > target) continue;
            bucket += nums[i];
            used |= 1 << i;
            if (backtrack(nums, i + 1, bucket, k, used, target)) return true;
            bucket -= nums[i];
            used ^= 1 << i;
        }
        return false;
    }
}

学习笔记：
这是一道标着中等的困难题，真把我做抑郁了。
说标中等因为搜索算法也可以算出来，但我用搜索算法每次跑到155/161个用例就超时。怎么改都不行只能更差不能更好。后来用了位运算，因为说了最多16个数字，所以用位运算来记录哪个数字用没用。
有空还是应该把这题搞懂搞清楚，太难了。