题目

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

题解

一上来以为是 dp（想到了左神讲的，将一个数组分成两个尽可能相等的部分那道题），再一想，原来是 backtracing。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        int target = sum / k;
        if (target * k != sum) return false;
        return process(nums, 0, new int[k], target);
    }

    public boolean process(int[] nums, int i, int[] bucket, int target) {
        if (i == nums.length) return true;

        for (int j = 0; j < bucket.length; j++) {
            if (bucket[j] + nums[i] <= target) {
                bucket[j] += nums[i];
                if (process(nums, i + 1, bucket, target)) return true;
                bucket[j] -= nums[i];
            }
        }
        return false;
    }
}

一把过，但是效率很低。