【综合笔试题】难度 3/5，多解法热门搜索题

忘是亡心i 2023-10-03 23:12 4阅读 0赞

![format_png][]

### 题目描述 ###

这是 LeetCode 上的 **[698. 划分为k个相等的子集][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) <= 161<=k<=len(nums)<=16
 *  0 < nums\[i\] < 100000<nums\[i\]<10000
 *  每个元素的频率在 \[1,4\]\[1,4\] 范围内

### 搜索 + 剪枝（贪心策略） ###

将 nn 个数均分成 kk 份，且 nn 与 kk 数据范围为 1616，容易想到搜索剪枝。

先对一些显然的无解情况进行分析：记 tot = \\sum\_\{i = 0\}^\{n - 1\}nums\[i\]tot=∑i=0n−1nums\[i\]，**若 tottot 不为 kk 的倍数，必然是无法实现均分，直接返回 `false`（可行性剪枝）**。同时可知单个集合的总和为 t = \\frac\{tot\}\{k\}t=ktot。

设计搜索函数为 `boolean dfs(int idx, int cur, int cnt, boolean[] vis)`，各项参数含义如下：

*  `cur` 为当前集合的元素和（初始值为 00）；
 *  `cnt` 是已凑成多少个总和为 tt 的集合（初始值为 00，当 cnt = kcnt=k 时，我们搜索到了合法方案，返回 `true`，否则对 `cnt` 进行加一操作，并将 `cur` 置零，搜索下个集合）；
 *  `vis` 用于记录哪些 nums\[i\]nums\[i\] 已被使用；
 *  `idx` 是搜索关键，其含义为搜索空间的分割点。即对于当前正在搜索的集合，我们不会每次都扫描整个 `nums` 来找添加到该集合的下一个元素，而是能够明确下一个元素必然在 idxidx 的左边或右边。 具体的，我们知道若最终存在合法方案，必然每个 nums\[i\]nums\[i\] 都均棣属于某个具体集合。我们考虑搜索某个集合的组成元素时，按照「从大到小」的方式进行搜索（起始先对 `nums` 进行排序），这样能够**确保若上一个被加入该集合的元素为 nums\[i\]nums\[i\]，则下一个被添加的元素 nums\[j\]nums\[j\] 必然位于 nums\[i\]nums\[i\] 的左边，即从下标 i - 1i−1 开始往前搜索（顺序性剪枝）**； 同时，也正是我们按照「从大到小」的方式进行搜索，**确保了当前集合的搜索，无须对已搜索到的集合进行调整**。 也就是说我们搜索的第一个集合是所有 nums\[i\]nums\[i\] 中的最大值所在的那个集合；二次搜索是所有 nums\[i\]nums\[i\] 减去第一个集合后剩余元素中最大值所在的集合 ... 这引导我们，**如果当前集合如果连第一个值都无法搜到（即剩余元素的最大值不能作为当前集合的元素），必然无解（可行性剪枝）**。

这样的「搜索 + 剪枝」的解法本质是利用了「贪心」来做策略：**我们每个回合的搜索总是在搜索「剩余未使用元素的最大值」所在的那个集合，并且按照「优先使用大数值」的原则来构造。**

可证明该做法的正确性：由于搜索的是「剩余未使用元素的最大值」所在的那个集合，因此剩余未使用元素必然在集合内，若被搜索到的其余元素参与集合构造导致有解变无解（即需要将其余元素进行替换才能确保有解），根据我们「从大到小」搜索下一个元素原则，替换过程必然不会使集合元素个数变少，即总是会拿不少于 KK 个的元素来替换当前集合的 KK 个元素（总和相同），从而可推断该替换并非必须。

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
    }
    复制代码

*  时间复杂度：爆搜剪枝不分析时空复杂度
 *  空间复杂度：爆搜剪枝不分析时空复杂度

### 模拟退火 ###

数据范围为 1616 自然也是很好的调参运用题。

**因为将 nn 个数划分为 kk 份，等效于用 nn 个数构造出一个「特定排列」，然后对「特定排列」进行固定模式的构造逻辑，就能实现「答案」与「目标排列」的对应关系。**

基于此，我们可以使用「模拟退火」进行求解。

单次迭代的基本流程：

1.  随机选择两个下标，计算「交换下标元素前对应序列的得分」&「交换下标元素后对应序列的得分」
2.  如果温度下降（交换后的序列更优），进入下一次迭代
3.  如果温度上升（交换前的序列更优），以「一定的概率」恢复现场（再交换回来）

我们可以制定如下规则来衡量当前排列与合法排列的差异程度：将当前的 `nums` 从前往后划分成总和不超过 tt 的 kk 份，并将 kk 份与 tt 的差值之和，作为对当前排列的差异程度评级 `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: number
    let ans: boolean
    let hi: number, lo: number, fa: number, N: number
    function 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 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：[github.com/SharingSour…][github.com_SharingSour] 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

[format_png]: https://img-blog.csdnimg.cn/img_convert/0ac86af8361cead4551562f3f6f3dd77.webp?x-oss-process=image/format,png
[698. _k]: https://link.juejin.cn/?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fpartition-to-k-equal-sum-subsets%2Fsolution%2Fby-ac_oier-mryw%2F
[github.com_SharingSour]: https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2FSharingSource%2FLogicStack-LeetCode