火柴拼正方形

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

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

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

(資料圖片)

示例 1:

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

示例 2:

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

提示:

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

思路

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

基于此，如果一個火柴數組能夠滿足構成正方形的基本條件，那再往下討論

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

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

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

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

那么怎么實現上述過程呢？用回溯

代碼回溯分析

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

1、確定回溯函數返回值和參數

根據分析，最終需要返回當前遍歷邊對應的edgeBox是否裝滿，所以要返回布爾值

輸入參數：matchsticks中火柴的下標stickIndex；matchsticks數組；存放4條邊的數組edgeBox；正方形的邊長edgeLen

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

2、確定終止條件

我們需要通過火柴下標stickIndex來判斷遞歸是否終止，因為本質上我們是用火柴去不斷嘗試放入edgeBox

如果遍歷到最后一根火柴，那么意味著其他火柴都被放到了合適的位置，目前就剩下一個位置給當前的火柴，返回true,結束，此時已經構成了正方形

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

3、處理單層邏輯

這部分需要不斷遍歷火柴累加至edgeBox數組的對應位置，并判斷當前edgeBox是否"裝滿"

沒裝滿就繼續觸發遞歸（此時還不會運行到返回true的位置），讓下一個火柴放入該edgeBox，直到放滿或者當前火柴無法放入

不管上述哪種情況，都會觸發回溯，將當前火柴拿到edgeBox數組的下一個位置（即下一條邊）繼續嘗試放入

若edgeBox數組遍歷結束都沒有返回true，那就返回false，說明當前火柴數組不能組成正方形

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

完整代碼

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

然后進行剪枝操作：對火柴數組進行排序，減少遞歸次數

步驟：

1、計算火柴數組元素和（正方形周長）

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

3、對火柴數組進行排序

4、定義edgeBox數組，調用遞歸函數

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

題外話：sort內置排序規則

greater表示內置類型從大到小排序，less表示內置類型從小到大排序。

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

剪枝

使用 劃分k個相等子集 中介紹的剪枝方法可以對本題代碼進行優化

優化版代碼

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

劃分k個相等子集

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

給定一個整數數組 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) <= 160 < nums[i] < 10000每個元素的頻率在 [1,4] 范圍內

思路

本題基本上就是 火柴拼正方形的抽象版，不同的是，火柴那題本質是求 劃分4個相等子集，而本題將需要劃分的子集個數拓展到了k個

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

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

所以，這里會側重討論剪枝的細節

基本思路再過一遍：

?1、先求出待劃分數組的元素總和，除以k，判斷是否能夠繼續進行劃分

?2、若數組元素總和能夠均分為k個子集，那么就遍歷待劃分數組元素，不斷嘗試放入子集數組中（過程使用遞歸回溯實現）

?3、當待劃分數組元素遍歷結束，劃分完成

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

和火柴那題一樣，返回值是布爾，參數是：待劃分數組nums、待劃分數組遍歷下標numsIndex，子集數組subBox，子集長度subLen

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

2、確定終止條件

終止條件也是一樣的：當待劃分數組遍歷下標numsIndex遍歷至最后一個元素，就結束。

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

3、確定單層處理邏輯

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

剪枝點1：如果當前subBox內的值與上一個subBox內的值相同，則可以跳過

什么意思呢？

subBox數組記錄的是什么？是當前某個子集中放了多少元素，總和為多少。

該剪枝點會在以下情況被觸發：

?一個待劃分數組的遍歷值經過嘗試無法放入當前subBox位置（例如subBox[2]），正在嘗試subBox中的下一個位置（例如subBox[3]）

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

除此之外，該剪枝點還將另外一種情況也給優化了，即：第一個待劃分數組的遍歷值放入subBox時，由于subBox元素均為0，所以放哪個都行，不用再去選擇了，直接令其放在第一個，這樣又節約了一些開銷

剪枝點2：提前計算一下放入當前待劃分數組遍歷值后，subBox對應位置的大小，如果超過我們需要的子集大小（subLen），那也可以直接跳過，不再進行后續的遞歸判斷

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

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

完整代碼

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

class Solution {private://確定遞歸函數參數和返回值    bool traversal(vector& nums, int numsIndex, vector& subBox, int subLen){        //確定終止條件        if(numsIndex == nums.size()) return true;        //確定單層處理邏輯        //用nums中的值去遍歷子集數組，嘗試放入        for(int i = 0; i < subBox.size(); ++i){            //剪枝點1：            if(i > 0 && subBox[i] == subBox[i - 1]) continue;            //剪枝點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) {        //計算整數數組nums的元素和        int numSum = 0;        for(auto num : nums) numSum += num;        if(numSum % k != 0) return false;        int subLen = numSum / k;        //把整數數組從大到小排序        sort(nums.begin(), nums.end(), greater());        //創建子集數組        vector subBox(k);        return traversal(nums, 0, subBox, subLen);    }};

公平發餅干

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

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

分發的 不公平程度 定義為單個孩子在分發過程中能夠獲得餅干的最大總數。

返回所有分發的最小不公平程度。

示例 1：

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

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

示例 2：

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

第 1 個孩子分到 [6,1] ，總計 6 + 1 = 7 塊餅干。第 2 個孩子分到 [3,2,2] ，總計 3 + 2 + 2 = 7 塊餅干。第 3 個孩子分到 [4,1,2] ，總計 4 + 1 + 2 = 7 塊餅干。分發的不公平程度為 max(7,7,7) = 7 。可以證明不存在不公平程度小于 7 的分發方案。

提示：

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

思路

本題的核心仍是對數組進行劃分，不同的是，這里劃分之后的結果可以是一些不相等的子集

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