首页 > itarticle > [leetcode] problem 698 – partition to k equal sum subsets

[leetcode] problem 698 – partition to k equal sum subsets

admin 11月 13, 2020 0

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example

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.

Note

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

Code

public boolean (int[] nums, int k) {
    int sum = 0;

    for (int num : nums)
        sum += num;

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

    boolean[] visit = new boolean[nums.length];

    Arrays.sort(nums);
    return dfs(nums, k, sum / k, 0, nums.length - 1, visit);
}

private boolean dfs(int[] nums, int k, int target, int sum, int idx, boolean[] visit) {
    if (k == 1)
        return true;

    if (sum > target)
        return false;

    if (sum == target)
        return dfs(nums, k - 1, target, 0, nums.length - 1, visit);

    for (int i = idx; i >= 0; i--) {
        if (visit[i])
            continue;

        visit[i] = true;

        if (dfs(nums, k, target, sum + nums[i], i - 1, visit))
            return true;

        visit[i] = false;
    }

    return false;
}