火柴拼正方形

https://leetcode.cn/problems/matchsticks-to-square/

你將得到一個(gè)整數(shù)數(shù)組 matchsticks ，其中 matchsticks[i] 是第 i 個(gè)火柴棒的長度。你要用 所有的火柴棍 拼成一個(gè)正方形。你 不能折斷 任何一根火柴棒，但你可以把它們連在一起，而且每根火柴棒必須 使用一次 。

如果你能使這個(gè)正方形，則返回 true ，否則返回 false 。

(資料圖片)

示例 1:

輸入: matchsticks = [1,1,2,2,2]輸出: true解釋: 能拼成一個(gè)邊長為2的正方形，每邊兩根火柴

示例 2:

輸入: matchsticks = [3,3,3,3,4]輸出: false解釋: 不能用所有火柴拼成一個(gè)正方形。

提示:

1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108

思路

首先，我們需要拼的是一個(gè)正方形，那么四邊都是相等的，由此我們可以先通過計(jì)算火柴數(shù)組matchsticks的元素總和（也就是正方形的周長），先判斷一下其能不能構(gòu)成正方形，不能就直接false了

基于此，如果一個(gè)火柴數(shù)組能夠滿足構(gòu)成正方形的基本條件，那再往下討論

我們可以把正方形的四條邊看成四個(gè)"邊容器"edgeBox

那么問題就變成了：從火柴數(shù)組中遍歷出值，往edgeBox中放，如果所有的火柴恰好能夠放滿所有的"邊容器"，那么該火柴數(shù)組就是可以構(gòu)成正方形的，過程如下：

在代碼實(shí)現(xiàn)時(shí)，我們可以用一個(gè)數(shù)組來定義edgeBox，這就是將邊看做一個(gè)"容器"的原因，即vector edgeBox(4);，正方形就4條邊，所以數(shù)組大小是固定的

剪枝點(diǎn)：此處例子雖然可以正好用最優(yōu)的遍歷次數(shù)解決問題，但很多情況下是會浪費(fèi)很多時(shí)間在“嘗試不適合的容器”上的，所以為了盡可能的提高性能，可以先把火柴數(shù)組從大到小排序

那么怎么實(shí)現(xiàn)上述過程呢？用回溯

代碼回溯分析

還記得回溯怎么寫吧?和遞歸一樣，也是三部曲

1、確定回溯函數(shù)返回值和參數(shù)

根據(jù)分析，最終需要返回當(dāng)前遍歷邊對應(yīng)的edgeBox是否裝滿，所以要返回布爾值

輸入?yún)?shù)：matchsticks中火柴的下標(biāo)stickIndex；matchsticks數(shù)組；存放4條邊的數(shù)組edgeBox；正方形的邊長edgeLen

class Solution {private://確定遞歸函數(shù)的參數(shù)與返回值    //根據(jù)分析，最終需要返回當(dāng)前遍歷邊對應(yīng)的edgeBox是否裝滿，所以要返回布爾值    //輸入?yún)?shù)：stickIndex；matchsticks；edgeBox；edgeLen    bool traversal(vector& matchsticks, int stickIndex, vector& edgeBox, int edgeLen){            }public:    bool makesquare(vector& matchsticks) {            }};

2、確定終止條件

我們需要通過火柴下標(biāo)stickIndex來判斷遞歸是否終止，因?yàn)楸举|(zhì)上我們是用火柴去不斷嘗試放入edgeBox

如果遍歷到最后一根火柴，那么意味著其他火柴都被放到了合適的位置，目前就剩下一個(gè)位置給當(dāng)前的火柴，返回true,結(jié)束，此時(shí)已經(jīng)構(gòu)成了正方形

class Solution {private://確定遞歸函數(shù)的參數(shù)與返回值    //根據(jù)分析，最終需要返回當(dāng)前遍歷邊對應(yīng)的edgeBox是否裝滿，所以要返回布爾值    //輸入?yún)?shù)：stickIndex；matchsticks；edgeBox；edgeLen    bool traversal(vector& matchsticks, int stickIndex, vector& edgeBox, int edgeLen){        //確定終止條件        //如果遍歷到最后一根火柴，就返回true,結(jié)束        if(stickIndex == matchsticks.size()) return true;    }public:    bool makesquare(vector& matchsticks) {            }};

3、處理單層邏輯

這部分需要不斷遍歷火柴累加至edgeBox數(shù)組的對應(yīng)位置，并判斷當(dāng)前edgeBox是否"裝滿"

沒裝滿就繼續(xù)觸發(fā)遞歸（此時(shí)還不會運(yùn)行到返回true的位置），讓下一個(gè)火柴放入該edgeBox，直到放滿或者當(dāng)前火柴無法放入

不管上述哪種情況，都會觸發(fā)回溯，將當(dāng)前火柴拿到edgeBox數(shù)組的下一個(gè)位置（即下一條邊）繼續(xù)嘗試放入

若edgeBox數(shù)組遍歷結(jié)束都沒有返回true，那就返回false，說明當(dāng)前火柴數(shù)組不能組成正方形

class Solution {private://確定遞歸函數(shù)的參數(shù)與返回值    //根據(jù)分析，最終需要返回當(dāng)前遍歷邊對應(yīng)的edgeBox是否裝滿，所以要返回布爾值    //輸入?yún)?shù)：stickIndex；matchsticks；edgeBox；edgeLen    bool traversal(vector& matchsticks, int stickIndex, vector& edgeBox, int edgeLen){        //確定終止條件        //如果遍歷到最后一根火柴，就返回true,結(jié)束        if(stickIndex == matchsticks.size()) return true;                //確定單層處理邏輯        //使用火柴遍歷edgeBox        for(int i = 0; i < edgeBox.size(); ++i){//遍歷edgeBox數(shù)組            edgeBox[i] += matchsticks[stickIndex];//試著把火柴放入當(dāng)前edgeBox            //做兩個(gè)判斷：1、當(dāng)前edgeBox是否已經(jīng)放滿；2、當(dāng)前edgeBox是否能放目前遍歷到的火柴            //沒放滿（小于等于）就可以繼續(xù)放            if(edgeBox[i] <= edgeLen && traversal(matchsticks, stickIndex + 1, edgeBox, edgeLen)) return true;            edgeBox[i] -= matchsticks[stickIndex];//回溯，如果不能放就把放入的挪走           }        return false;    }public:    bool makesquare(vector& matchsticks) {            }};

完整代碼

在主函數(shù)部分，需要計(jì)算火柴數(shù)組元素和（正方形周長），判斷周長是否滿足條件

然后進(jìn)行剪枝操作：對火柴數(shù)組進(jìn)行排序，減少遞歸次數(shù)

步驟：

1、計(jì)算火柴數(shù)組元素和（正方形周長）

2、判斷周長是否滿足條件

3、對火柴數(shù)組進(jìn)行排序

4、定義edgeBox數(shù)組，調(diào)用遞歸函數(shù)

class Solution {private://確定遞歸函數(shù)的參數(shù)與返回值    bool traversal(vector& matchsticks, int stickIndex, vector& edgeBox, int edgeLen){        //確定終止條件        //如果遍歷到最后一根火柴，就返回true,結(jié)束        if(stickIndex == matchsticks.size()) return true;        //確定單層處理邏輯        //使用火柴遍歷edgeBox        for(int i = 0; i < edgeBox.size(); ++i){            edgeBox[i] += matchsticks[stickIndex];//試著把火柴放入當(dāng)前edgeBox            //做兩個(gè)判斷：1、當(dāng)前edgeBox是否已經(jīng)放滿；2、當(dāng)前edgeBox是否能放目前遍歷到的火柴            //沒放滿（小于等于）就可以繼續(xù)放            if(edgeBox[i] <= edgeLen && traversal(matchsticks, stickIndex + 1, edgeBox, edgeLen)) return true;            edgeBox[i] -= matchsticks[stickIndex];//回溯，如果不能放就把放入的挪走           }        return false;    }public:    bool makesquare(vector& matchsticks) {        //計(jì)算火柴數(shù)組元素和（正方形周長）        int matchstickSum = 0;        for(auto stick : matchsticks) matchstickSum += stick;        //判斷周長是否滿足條件        if(matchstickSum % 4 != 0) return false;        //計(jì)算正方形邊長        // int edgeLen = matchstickSum / 4;        //對火柴數(shù)組進(jìn)行排序，減少遞歸次數(shù)        sort(matchsticks.begin(), matchsticks.end(), greater());//        //定義一個(gè)數(shù)組用于表示正方形的四條邊        vector edgeBox(4);//數(shù)組大小為4        //調(diào)用遞歸函數(shù)        return traversal(matchsticks, 0, edgeBox, matchstickSum / 4);    }};

題外話：sort內(nèi)置排序規(guī)則

greater表示內(nèi)置類型從大到小排序，less表示內(nèi)置類型從小到大排序。

sort(matchsticks.begin(), matchsticks.end(), greater());//從大到小sort(matchsticks.begin(), matchsticks.end(), less());//從小到大

剪枝

使用 劃分k個(gè)相等子集 中介紹的剪枝方法可以對本題代碼進(jìn)行優(yōu)化

優(yōu)化版代碼

class Solution {private://確定遞歸函數(shù)的參數(shù)與返回值    bool traversal(vector& matchsticks, int stickIndex, vector& edgeBox, int edgeLen){        //確定終止條件        //如果遍歷到最后一根火柴，就返回true,結(jié)束        if(stickIndex == matchsticks.size()) return true;        //確定單層處理邏輯        //使用火柴遍歷edgeBox        for(int i = 0; i < edgeBox.size(); ++i){            //剪枝優(yōu)化            if(i > 0 && edgeBox[i] == edgeBox[i - 1]) continue;            if(edgeBox[i] + matchsticks[stickIndex] > edgeLen) continue;            edgeBox[i] += matchsticks[stickIndex];//試著把火柴放入當(dāng)前edgeBox            //做兩個(gè)判斷：1、當(dāng)前edgeBox是否已經(jīng)放滿；2、當(dāng)前edgeBox是否能放目前遍歷到的火柴            //沒放滿（小于等于）就可以繼續(xù)放            if(edgeBox[i] <= edgeLen && traversal(matchsticks, stickIndex + 1, edgeBox, edgeLen)) return true;            edgeBox[i] -= matchsticks[stickIndex];//回溯，如果不能放就把放入的挪走           }        return false;    }public:    bool makesquare(vector& matchsticks) {        //計(jì)算火柴數(shù)組元素和（正方形周長）        int matchstickSum = 0;        for(auto stick : matchsticks) matchstickSum += stick;        //判斷周長是否滿足條件        if(matchstickSum % 4 != 0) return false;        //計(jì)算正方形邊長        // int edgeLen = matchstickSum / 4;        //對火柴數(shù)組進(jìn)行排序，減少遞歸次數(shù)        sort(matchsticks.begin(), matchsticks.end(), greater());//        //定義一個(gè)數(shù)組用于表示正方形的四條邊        vector edgeBox(4);//數(shù)組大小為4        //調(diào)用遞歸函數(shù)        return traversal(matchsticks, 0, edgeBox, matchstickSum / 4);    }};

劃分k個(gè)相等子集

https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) k，找出是否有可能把這個(gè)數(shù)組分成 k 個(gè)非空子集，其總和都相等。

示例 1：

輸入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4輸出： True說明： 有可能將其分成 4 個(gè)子集（5），（1,4），（2,3），（2,3）等于總和。

示例 2:

輸入: nums = [1,2,3,4], k = 3輸出: false

提示：

1 <= k <= len(nums) <= 160 < nums[i] < 10000每個(gè)元素的頻率在 [1,4] 范圍內(nèi)

思路

本題基本上就是 火柴拼正方形的抽象版，不同的是，火柴那題本質(zhì)是求 劃分4個(gè)相等子集，而本題將需要?jiǎng)澐值淖蛹瘋€(gè)數(shù)拓展到了k個(gè)

好消息是，這兩題的思路基本可以復(fù)用；壞消息是，采用一般的遞歸回溯方式解本題會超時(shí)

因此，需要引入一些剪枝操作來降低處理成本

所以，這里會側(cè)重討論剪枝的細(xì)節(jié)

基本思路再過一遍：

?1、先求出待劃分?jǐn)?shù)組的元素總和，除以k，判斷是否能夠繼續(xù)進(jìn)行劃分

?2、若數(shù)組元素總和能夠均分為k個(gè)子集，那么就遍歷待劃分?jǐn)?shù)組元素，不斷嘗試放入子集數(shù)組中（過程使用遞歸回溯實(shí)現(xiàn)）

?3、當(dāng)待劃分?jǐn)?shù)組元素遍歷結(jié)束，劃分完成

代碼回溯分析1、確定回溯函數(shù)的參數(shù)與返回值

和火柴那題一樣，返回值是布爾，參數(shù)是：待劃分?jǐn)?shù)組nums、待劃分?jǐn)?shù)組遍歷下標(biāo)numsIndex，子集數(shù)組subBox，子集長度subLen

class Solution {private://確定遞歸函數(shù)參數(shù)和返回值    bool traversal(vector& nums, int numsIndex, vector& subBox, int subLen){            }public:    bool canPartitionKSubsets(vector& nums, int k) {            }};

2、確定終止條件

終止條件也是一樣的：當(dāng)待劃分?jǐn)?shù)組遍歷下標(biāo)numsIndex遍歷至最后一個(gè)元素，就結(jié)束。

class Solution {private://確定遞歸函數(shù)參數(shù)和返回值    bool traversal(vector& nums, int numsIndex, vector& subBox, int subLen){        //確定終止條件        if(numsIndex == nums.size()) return true;            }public:    bool canPartitionKSubsets(vector& nums, int k) {            }};

3、確定單層處理邏輯

這里是重點(diǎn)了，雖然邏輯是可以直接套用火柴那題的，但是需要做一定的剪枝才能ac

剪枝點(diǎn)1：如果當(dāng)前subBox內(nèi)的值與上一個(gè)subBox內(nèi)的值相同，則可以跳過

什么意思呢？

subBox數(shù)組記錄的是什么？是當(dāng)前某個(gè)子集中放了多少元素，總和為多少。

該剪枝點(diǎn)會在以下情況被觸發(fā)：

?一個(gè)待劃分?jǐn)?shù)組的遍歷值經(jīng)過嘗試無法放入當(dāng)前subBox位置（例如subBox[2]），正在嘗試subBox中的下一個(gè)位置（例如subBox[3]）

如果下一個(gè)位置（例如subBox[3]）所記錄的元素總和等于上一個(gè)位置（例如subBox[2]）的，那么其實(shí)該元素還是放不進(jìn)，因此就沒有必要再去執(zhí)行下面 "嘗試放入數(shù)組" 的操作了，可以直接去試subBox的下一個(gè)位置，從而提高了性能

除此之外，該剪枝點(diǎn)還將另外一種情況也給優(yōu)化了，即：第一個(gè)待劃分?jǐn)?shù)組的遍歷值放入subBox時(shí)，由于subBox元素均為0，所以放哪個(gè)都行，不用再去選擇了，直接令其放在第一個(gè)，這樣又節(jié)約了一些開銷

剪枝點(diǎn)2：提前計(jì)算一下放入當(dāng)前待劃分?jǐn)?shù)組遍歷值后，subBox對應(yīng)位置的大小，如果超過我們需要的子集大小（subLen），那也可以直接跳過，不再進(jìn)行后續(xù)的遞歸判斷

class Solution {private://確定遞歸函數(shù)參數(shù)和返回值    bool traversal(vector& nums, int numsIndex, vector& subBox, int subLen){        //確定終止條件        if(numsIndex == nums.size()) return true;        //確定單層處理邏輯        //用nums中的值去遍歷子集數(shù)組，嘗試放入        for(int i = 0; i < subBox.size(); ++i){            //剪枝點(diǎn)1            if(i > 0 && subBox[i] == subBox[i - 1]) continue;            //剪枝點(diǎn)2            if(subBox[i] + nums[numsIndex] > subLen) continue;            subBox[i] += nums[numsIndex];            if(subBox[i] <= subLen && traversal(nums, numsIndex + 1, subBox, subLen)) return true;            subBox[i] -= nums[numsIndex];        }        return false;    }public:    bool canPartitionKSubsets(vector& nums, int k) {    }};

本質(zhì)上，此處的剪枝操作都是在遞歸判斷之前，人為的篩選掉一些情況，減少觸發(fā)遞歸的次數(shù)，進(jìn)而提升性能

完整代碼

主函數(shù)部分的邏輯與火柴那題完全一致，就不多說了

class Solution {private://確定遞歸函數(shù)參數(shù)和返回值    bool traversal(vector& nums, int numsIndex, vector& subBox, int subLen){        //確定終止條件        if(numsIndex == nums.size()) return true;        //確定單層處理邏輯        //用nums中的值去遍歷子集數(shù)組，嘗試放入        for(int i = 0; i < subBox.size(); ++i){            //剪枝點(diǎn)1：            if(i > 0 && subBox[i] == subBox[i - 1]) continue;            //剪枝點(diǎn)2            if(subBox[i] + nums[numsIndex] > subLen) continue;            subBox[i] += nums[numsIndex];//嘗試放入待劃分?jǐn)?shù)組的遍歷值            if(subBox[i] <= subLen && traversal(nums, numsIndex + 1, subBox, subLen)) return true;            subBox[i] -= nums[numsIndex];//不滿足條件就不能放進(jìn)來，因此要回溯        }        return false;    }public:    bool canPartitionKSubsets(vector& nums, int k) {        //計(jì)算整數(shù)數(shù)組nums的元素和        int numSum = 0;        for(auto num : nums) numSum += num;        if(numSum % k != 0) return false;        int subLen = numSum / k;        //把整數(shù)數(shù)組從大到小排序        sort(nums.begin(), nums.end(), greater());        //創(chuàng)建子集數(shù)組        vector subBox(k);        return traversal(nums, 0, subBox, subLen);    }};

公平發(fā)餅干

https://leetcode.cn/problems/fair-distribution-of-cookies/

給你一個(gè)整數(shù)數(shù)組 cookies ，其中 cookies[i] 表示在第 i 個(gè)零食包中的餅干數(shù)量。另給你一個(gè)整數(shù) k 表示等待分發(fā)零食包的孩子數(shù)量，所有 零食包都需要分發(fā)。在同一個(gè)零食包中的所有餅干都必須分發(fā)給同一個(gè)孩子，不能分開。

分發(fā)的 不公平程度 定義為單個(gè)孩子在分發(fā)過程中能夠獲得餅干的最大總數(shù)。

返回所有分發(fā)的最小不公平程度。

示例 1：

輸入：cookies = [8,15,10,20,8], k = 2輸出：31解釋：一種最優(yōu)方案是 [8,15,8] 和 [10,20] 。

第 1 個(gè)孩子分到 [8,15,8] ，總計(jì) 8 + 15 + 8 = 31 塊餅干。第 2 個(gè)孩子分到 [10,20] ，總計(jì) 10 + 20 = 30 塊餅干。分發(fā)的不公平程度為 max(31,30) = 31 。可以證明不存在不公平程度小于 31 的分發(fā)方案。

示例 2：

輸入：cookies = [6,1,3,2,2,4,1,2], k = 3輸出：7解釋：一種最優(yōu)方案是 [6,1]、[3,2,2] 和 [4,1,2] 。

第 1 個(gè)孩子分到 [6,1] ，總計(jì) 6 + 1 = 7 塊餅干。第 2 個(gè)孩子分到 [3,2,2] ，總計(jì) 3 + 2 + 2 = 7 塊餅干。第 3 個(gè)孩子分到 [4,1,2] ，總計(jì) 4 + 1 + 2 = 7 塊餅干。分發(fā)的不公平程度為 max(7,7,7) = 7 ?？梢宰C明不存在不公平程度小于 7 的分發(fā)方案。

提示：

2 <= cookies.length <= 81 <= cookies[i] <= 1052 <= k <= cookies.length

思路

本題的核心仍是對數(shù)組進(jìn)行劃分，不同的是，這里劃分之后的結(jié)果可以是一些不相等的子集

但是，需要使這些子集之間的差值盡量的小TBD