Java实现 LeetCode 698 划分为k个相等的子集(递归)

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输出： True

说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

注意:

1 <= k <= len(nums) <= 16

0 < nums[i] < 10000

class Solution {

    int K = 0, N = 0;

    public boolean canPartitionKSubsets(int[] nums, int k) {

		int n = nums.length, sum = 0, eachSum = 0;

		if (n == 0 || k == 0)

			return false;

		N = n;

		K = k;

		int[] arr = new int[k];

		for (int i : nums)

			sum += i;

		if (sum % k != 0)

			return false;

		eachSum = sum / k;

		Arrays.fill(arr, eachSum);

		Arrays.sort(nums);

		return helper(nums, n-1, arr);

	}

	boolean helper(int[] nums, int cur, int[] arr) {

		if (cur < 0)

			return true;

		int temp = nums[cur];

		for (int i = 0; i < K; i++) {

			if (arr[i] == temp || (cur > 0 && arr[i] - temp >= nums[0])) {

				arr[i] -= temp;

				if (helper(nums, cur - 1, arr)) {

					return true;

				}

				arr[i] += temp;

			}

		}

		return false;

	}

}

巴特西

Java实现 LeetCode 698 划分为k个相等的子集(递归)

698. 划分为k个相等的子集

最新文章

热门文章