[leetcode #698] Partition to K Equal Sum Subsets

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⁴
・ The frequency of each element is in the range [1, 4].

Idea

似たような問題は以前も解決できなかったようで、今回も解決できなかった.再帰関数で遡及する問題は私にとっていつも難しいようだ.グーグルの助けで解題方法を確認せざるを得なかった.setを作成し、setの和が特定の値であるかどうかを逐一決定するには、遡及のみを行う方法はありません.最初はmapで各値と周波数を格納し、すべての場合の数字を確認しようとしましたが、複雑すぎるようで諦めました.
まず所与の数の和を求め,k個で割った値を各サブセットの和(share)とする.このとき、残りが0でない場合は、すぐにfalseに戻ります.
与えられた数値を昇順に並べ替えた後、shareと同じ値を後の値から除外します.このときkの値も1だけ低下する.
残りの値は、共有する前に要素が2より大きいsetを作成する必要がある場合があります.この可能性を確認するために再帰関数を用いた.
再帰関数のアルゴリズムは次のとおりです.

last indexが0未満の場合、trueが返されます.

Bucketの値が残りの最大値に加算されたときにシェア以下であるかどうかを決定します.
a.上記の条件を満たす場合、bucketに対応する値を追加します.
b.最後のindexを下げて再帰関数を呼び出す.再帰関数がtrueを返すと、同様にtrueが返されます.
c.再帰関数がfalseを返すとbucketから値が減算されます.
d.上記の手順でbucket値が0の場合はfalseを返します.

のすべてのbucketが入力され、共有値以外のbucketが表示された場合、falseが返されます.

Solution

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 1. get share and return false when remainder is not zero
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int share = sum / k;
        if (sum % k > 0)
            return false;

        // 2. sort array
        Arrays.sort(nums);

        // 3. make bucket and check whether share can be put in each buckets
        int last = nums.length - 1;
        while (last >= 0 && nums[last] == share) {
            last--;
            k--;
        }
        int[] buckets = new int[k];
        return divideToBuckets(nums, buckets, last, share);
    }

    private boolean divideToBuckets(int[] nums, int[] buckets, int last, int share) {
        if (last < 0)
            return true;

        for (int i=0; i < buckets.length; i++) {
            if (buckets[i] + nums[last] <= share) {
            	buckets[i] += nums[last];
                if (divideToBuckets(nums, buckets, last-1, share))
                    return true;
                buckets[i] -= nums[last];
            }
            if (buckets[i] == 0)
                break;
    	}

    	return false;
    }
}

Reference

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
https://www.programcreek.com/2014/02/leetcode-partition-to-k-equal-sum-subsets-java/