Problem
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into knon-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.
Note:
1 <= k <= len(nums) <= 16.0 < nums[i] < 10000.
Solution: Search
Time complexity: O(n!)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 4 ms (<99.21%) class Solution { public: bool canPartitionKSubsets(vector<int>& nums, int k) { const int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % k != 0) return false; sort(nums.rbegin(), nums.rend()); return dfs(nums, sum / k, 0, k, 0); } private: bool dfs(const vector<int>& nums, int target, int cur, int k, int used) { if (k == 0) return used == (1 << nums.size()) - 1; for (int i = 0; i < nums.size(); ++i) { if (used & (1 << i)) continue; int t = cur + nums[i]; if (t > target) break; // Important int new_used = used | (1 << i); if (t == target && dfs(nums, target, 0, k - 1, new_used)) return true; else if (dfs(nums, target, t, k, new_used)) return true; } return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment