3妹：2哥，本日周日，出去玩一玩，爬登山怎么样。
2哥：还出去玩呢，如今天下疫情又反复了， 前段时间上海疫情刚控制住，如今宿州泗县和无锡疫情又发作了，照旧留意一些，不要任意出去走动了。
3妹：哦，是哦，平凡公民能做的就是只管居家，不能防疫添贫苦。
2哥：对，照旧在家打会儿游戏吧，来，带你打野。
3妹：切，我对打游戏没爱好，我照旧做几道题，然后看我的韩剧吧
题目：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相称。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
分析： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）便是总和。
示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false
提示：
1 <= k <= len(nums) <= 16
0 < nums < 10000
每个元素的频率在 [1,4] 范围内
java代码：
class Solution { int[] nums; int per, n; boolean[] dp; public boolean canPartitionKSubsets(int[] nums, int k) { this.nums = nums; int all = Arrays.stream(nums).sum(); if (all % k != 0) { return false; } per = all / k; Arrays.sort(nums); n = nums.length; if (nums[n - 1] > per) { return false; } dp = new boolean[1 << n]; Arrays.fill(dp, true); return dfs((1 << n) - 1, 0); } public boolean dfs(int s, int p) { if (s == 0) { return true; } if (!dp) { return dp; } dp = false; for (int i = 0; i < n; i++) { if (nums + p > per) { break; } if (((s >> i) & 1) != 0) { if (dfs(s ^ (1 << i), (p + nums) % per)) { return true; } } } return false; }} |
