题目形容
这是 LeetCode 上的 698. 划分为k个相等的子集 ，难度为 中等。
Tag : 「搜寻」、「爆搜」、「剪枝」、「模拟退火」、「启发式搜寻」、「回溯算法」、「贪婪」
给定一个整数数组 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[i] < 10000$
- 每个元素的频率在 $[1,4]$ 范畴内
搜寻 + 剪枝（贪婪策略）
将 $n$ 个数均分成 $k$ 份，且 $n$ 与 $k$ 数据范畴为 $16$，容易想到搜寻剪枝。
先对一些显然的无解状况进行剖析：记 $tot = \sum_{i = 0}^{n - 1}nums[i]$，若 $tot$ 不为 $k$ 的倍数，必然是无奈实现均分，间接返回 false（可行性剪枝）。同时可知单个汇合的总和为 $t = \frac{tot}{k}$。
设计搜寻函数为 boolean dfs(int idx, int cur, int cnt, boolean[] vis)，各项参数含意如下：
cur为以后汇合的元素和（初始值为 $0$）；cnt是已凑成多少个总和为 $t$ 的汇合（初始值为 $0$，当 $cnt = k$ 时，咱们搜寻到了非法计划，返回true，否则对cnt进行加一操作，并将cur置零，搜寻下个汇合）；vis用于记录哪些 $nums[i]$ 已被应用；idx是搜寻要害，其含意为搜寻空间的宰割点。即对于以后正在搜寻的汇合，咱们不会每次都扫描整个nums来找增加到该汇合的下一个元素，而是可能明确下一个元素必然在 $idx$ 的右边或左边。
具体的，咱们晓得若最终存在非法计划，必然每个 $nums[i]$ 都均棣属于某个具体汇合。咱们思考搜寻某个汇合的组成元素时，依照「从大到小」的形式进行搜寻（起始先对nums进行排序），这样可能确保若上一个被退出该汇合的元素为 $nums[i]$，则下一个被增加的元素 $nums[j]$ 必然位于 $nums[i]$ 的右边，即从下标 $i - 1$ 开始往前搜寻（程序性剪枝）；
同时，也正是咱们依照「从大到小」的形式进行搜寻，确保了以后汇合的搜寻，毋庸对已搜寻到的汇合进行调整。
也就是说咱们搜寻的第一个汇合是所有 $nums[i]$ 中的最大值所在的那个汇合；二次搜寻是所有 $nums[i]$ 减去第一个汇合后残余元素中最大值所在的汇合 ...
这疏导咱们，如果以后汇合如果连第一个值都无奈搜到（即残余元素的最大值不能作为以后汇合的元素），必然无解（可行性剪枝）。
这样的「搜寻 + 剪枝」的解法实质是利用了「贪婪」来做策略：咱们每个回合的搜寻总是在搜寻「残余未应用元素的最大值」所在的那个汇合，并且依照「优先应用大数值」的准则来结构。
可证实该做法的正确性：因为搜寻的是「残余未应用元素的最大值」所在的那个汇合，因而残余未应用元素必然在汇合内，若被搜寻到的其余元素参加汇合结构导致有解变无解（即须要将其余元素进行替换能力确保有解），依据咱们「从大到小」搜寻下一个元素准则，替换过程必然不会使汇合元素个数变少，即总是会拿不少于 $K$ 个的元素来替换以后汇合的 $K$ 个元素（总和雷同），从而可推断该替换并非必须。
Java 代码：
class Solution { int[] nums; int n, t, k; public boolean canPartitionKSubsets(int[] _nums, int _k) { nums = _nums; k = _k; int tot = 0; for (int x : nums) tot += x; if (tot % k != 0) return false; // 可行性剪枝 Arrays.sort(nums); n = nums.length; t = tot / k; return dfs(n - 1, 0, 0, new boolean[n]); } boolean dfs(int idx, int cur, int cnt, boolean[] vis) { if (cnt == k) return true; if (cur == t) return dfs(n - 1, 0, cnt + 1, vis); for (int i = idx; i >= 0; i--) { // 程序性剪枝 if (vis[i] || cur + nums[i] > t) continue; // 可行性剪枝 vis[i] = true; if (dfs(i - 1, cur + nums[i], cnt, vis)) return true; vis[i] = false; if (cur == 0) return false; // 可行性剪枝 } return false; }}TypeScript 代码：
let nums: number[];let n: number, t: number, k: number;function canPartitionKSubsets(_nums: number[], _k: number): boolean { nums = _nums; k = _k; let tot = 0 for (let x of nums) tot += x if (tot % k != 0) return false nums.sort((a,b)=>a-b) n = nums.length; t = tot / k return dfs(n - 1, 0, 0, new Array<boolean>(n).fill(false))};function dfs(idx: number, cur: number, cnt: number, vis: boolean[]): boolean { if (cnt == k) return true if (cur == t) return dfs(n - 1, 0, cnt + 1, vis) for (let i = idx; i >= 0; i--) { if (vis[i] || cur + nums[i] > t) continue vis[i] = true if (dfs(idx - 1, cur + nums[i], cnt, vis)) return true vis[i] = false if (cur == 0) return false } return false}- 工夫复杂度：爆搜剪枝不剖析时空复杂度
- 空间复杂度：爆搜剪枝不剖析时空复杂度
模拟退火
数据范畴为 $16$ 天然也是很好的调参使用题。
因为将 $n$ 个数划分为 $k$ 份，等效于用 $n$ 个数结构出一个「特定排列」，而后对「特定排列」进行固定模式的结构逻辑，就能实现「答案」与「指标排列」的对应关系。
基于此，咱们能够应用「模拟退火」进行求解。
单次迭代的根本流程：
- 随机抉择两个下标，计算「替换下标元素前对应序列的得分」&「替换下标元素后对应序列的得分」
- 如果温度降落（替换后的序列更优），进入下一次迭代
- 如果温度回升（替换前的序列更优），以「肯定的概率」复原现场（再替换回来）
咱们能够制订如下规定来掂量以后排列与非法排列的差别水平：将以后的 nums 从前往后划分成总和不超过 $t$ 的 $k$ 份，并将 $k$ 份与 $t$ 的差值之和，作为对以后排列的差别水平评级 diff，当呈现 diff = 0 阐明找到了非法排列，可完结搜寻。
该计算规定可确保排列变动的间断性能无效体现在 diff 数值上。
Java 代码（2022/09/20 可通过）：
class Solution { int[] nums; int n, tval, k; Random random = new Random(20220920); double hi = 1e9, lo = 1e-4, fa = 0.95; int N = 600; boolean ans; int calc() { int diff = tval * k; for (int i = 0, j = 0; i < n && j < k; j++) { int cur = 0; while (i < n && cur + nums[i] <= tval) cur += nums[i++]; diff -= cur; } if (diff == 0) ans = true; return diff; } void sa() { shuffle(nums); for (double t = hi; t > lo && !ans; t *= fa) { int a = random.nextInt(n), b = random.nextInt(n); if (a == b) continue; int prev = calc(); swap(nums, a, b); int cur = calc(); int diff = cur - prev; if (Math.log(diff / t) > random.nextDouble()) swap(nums, a, b); } } public boolean canPartitionKSubsets(int[] _nums, int _k) { nums = _nums; k = _k; int tot = 0; for (int x : nums) tot += x; if (tot % k != 0) return false; n = nums.length; tval = tot / k; while (!ans && N-- > 0) sa(); return ans; } void shuffle(int[] nums) { for (int i = n; i > 0; i--) swap(nums, random.nextInt(i), i - 1); } void swap(int[] nums, int a, int b) { int c = nums[a]; nums[a] = nums[b]; nums[b] = c; }}TypeScript 代码（2022/09/20 可通过）：
let nums: number[];let n: number, tval: number, k: numberlet ans: booleanlet hi: number, lo: number, fa: number, N: numberfunction getRandom(max: number): number { return Math.floor(Math.random() * (max + 1))}function calc(): number { let diff = tval * k for (let i = 0, j = 0; i < n && j < k; j++) { let cur = 0 while (i < n && cur + nums[i] <= tval) cur += nums[i++] diff -= cur } if (diff == 0) ans = true return diff}function sa(): void { shuffle(nums) for (let t = hi; t > lo && !ans; t *= fa) { const a = getRandom(n - 1), b = getRandom(n - 1) if (a == b) continue const prev = calc() swap(nums, a, b) const cur = calc() const diff = cur - prev if (Math.log(diff / t) > Math.random()) swap(nums, a, b) }}function canPartitionKSubsets(_nums: number[], _k: number): boolean { nums = _nums; k = _k let tot = 0 for (let x of nums) tot += x if (tot % k != 0) return false n = nums.length; tval = tot / k hi = 1e9; lo = 1e-4; fa = 0.98; N = 700 ans = false while (!ans && N-- > 0) sa() return ans}function shuffle(nums: number[]): void { for (let i = n; i > 0; i--) swap(nums, getRandom(i), i - 1)}function swap(nums: number[], a: number, b: number): void { const c = nums[a] nums[a] = nums[b] nums[b] = c}- 工夫复杂度：启发式搜寻不剖析时空复杂度
- 空间复杂度：启发式搜寻不剖析时空复杂度
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.698 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布