leetcode 698. Partition to K Equal Sum Subsets | 698. 划分为k个相等的子集（回溯法）

本文主要是介绍leetcode 698. Partition to K Equal Sum Subsets | 698. 划分为k个相等的子集（回溯法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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;}
}

一把过，但是效率很低。

这篇关于leetcode 698. Partition to K Equal Sum Subsets | 698. 划分为k个相等的子集（回溯法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---