[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

비슷한 문제를 예전에도 못 풀었던 것 같은데 이번에도 결국 못 풀고 말았다. 재귀함수로 backtracking하는 문제는 나에게 언제나 어려운 것 같다. 어쩔 수 없이 구글의 도움을 받아 문제를 푸는 방법을 확인했다. set을 만들고 해당 set의 합이 특정 값이 되는지 일일이 확인하기 위해서는 backtracking만한 방법이 없다. 처음에는 map을 이용해 각 값과 빈도수를 저장하고 모든 경우의 수를 확인해보려 했지만 너무 복잡한 거 같아 포기하고 말았다.

우선 주어진 수들의 합을 구하고 k개로 나눈 값을 각 subset의 합 (share)으로 정한다. 이 때 나머지가 0이 아니라면 바로 false를 리턴하면 된다.

주어진 수를 오름차 순으로 정렬한 뒤, 뒤의 값들 중 share와 똑같은 값은 제외시킨다. 이 때 k의 값도 1씩 낮춰준다.

남은 값들은 원소가 2개 이상인 set을 만들어야 합이 share가 될 가능성이 있다. 이 가능성을 확인하기 위해 재귀함수를 활용한다.

재귀함수의 알고리즘은 다음과 같다.

1. last index가 0보다 작을 경우 true를 리턴한다.
2. Bucket의 값과 남은 수 중 가장 큰 값을 더했을 때 share보다 작거나 같은지 확인한다.
   a. 위 조건을 충족시킨다면 bucket에 해당 값을 더한다.
   b. 마지막 index를 낮추어 재귀함수를 호출한다. 재귀함수가 true를 리턴하면 똑같이 true를 리턴한다.
   c. 재귀함수가 false를 리턴할 경우 bucket에 더한 값을 뺀다.
   d. 위 과정 중 bucket 값이 0이 될 경우 false를 리턴한다.
3. 모든 bucket을 채웠음에도 share값이 아닌 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/