[LeetCode回溯算法#extra01]集合划分问题[火柴拼正方形/划分k个相等子集/公平发饼干]

火柴拼正方形

你将得到一个整数数组 matchsticks，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴

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

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

思路

四边都是相等的，由此我们可以先通过计算火柴数组matchsticks的元素总和（也就是正方形的周长），先判断一下其能不能构成正方形，不能就直接false了

我们可以把正方形的四条边看成四个"边容器"edgeBox

从火柴数组中遍历出值，往edgeBox中放，如果所有的火柴恰好能够放满所有的"边容器"，那么该火柴数组就是可以构成正方形的，过程如下：

vector<int> edgeBox(4;，正方形就4条边，所以数组大小是固定的

从大到小排序

回溯

代码

回溯分析

1、确定回溯函数返回值和参数

根据分析，最终需要返回当前遍历边对应的edgeBox是否装满，所以要返回布尔值

stickIndex；matchsticks数组；存放4条边的数组edgeBox；正方形的边长edgeLen

class Solution {
private://确定递归函数的参数与返回值
    //根据分析，最终需要返回当前遍历边对应的edgeBox是否装满，所以要返回布尔值
    //输入参数：stickIndex；matchsticks；edgeBox；edgeLen
    bool traversal(vector<int>& matchsticks, int stickIndex, vector<int>& edgeBox, int edgeLen{
        
    }
public:
    bool makesquare(vector<int>& matchsticks {
        
    }
};

2、确定终止条件

我们需要通过火柴下标stickIndex来判断递归是否终止，因为本质上我们是用火柴去不断尝试放入edgeBox

class Solution {
private://确定递归函数的参数与返回值
    //根据分析，最终需要返回当前遍历边对应的edgeBox是否装满，所以要返回布尔值
    //输入参数：stickIndex；matchsticks；edgeBox；edgeLen
    bool traversal(vector<int>& matchsticks, int stickIndex, vector<int>& edgeBox, int edgeLen{
        //确定终止条件
        //如果遍历到最后一根火柴，就返回true,结束
        if(stickIndex == matchsticks.size( return true;
    }
public:
    bool makesquare(vector<int>& matchsticks {
        
    }
};

3、处理单层逻辑

这部分需要不断遍历火柴累加至edgeBox数组的对应位置，并判断当前edgeBox是否"装满"

放满或者当前火柴无法放入

不管上述哪种情况，都会触发回溯，将当前火柴拿到edgeBox数组的下一个位置（即下一条边）继续尝试放入

class Solution {
private://确定递归函数的参数与返回值
    //根据分析，最终需要返回当前遍历边对应的edgeBox是否装满，所以要返回布尔值
    //输入参数：stickIndex；matchsticks；edgeBox；edgeLen
    bool traversal(vector<int>& matchsticks, int stickIndex, vector<int>& 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<int>& matchsticks {
        
    }
};

完整代码

在主函数部分，需要计算火柴数组元素和（正方形周长），判断周长是否满足条件

步骤：

2、判断周长是否满足条件

4、定义edgeBox数组，调用递归函数

class Solution {
private://确定递归函数的参数与返回值
    bool traversal(vector<int>& matchsticks, int stickIndex, vector<int>& 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<int>& 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<int>(;//

        //定义一个数组用于表示正方形的四条边
        vector<int> edgeBox(4;//数组大小为4

        //调用递归函数
        return traversal(matchsticks, 0, edgeBox, matchstickSum / 4;
    }
};

题外话：sort内置排序规则

greater表示内置类型从大到小排序，less表示内置类型从小到大排序。

sort(matchsticks.begin(, matchsticks.end(, greater<int>(;//从大到小
sort(matchsticks.begin(, matchsticks.end(, less<int>(;//从小到大

剪枝

使用 划分k个相等子集 中介绍的剪枝方法可以对本题代码进行优化

优化版代码

class Solution {
private://确定递归函数的参数与返回值
    bool traversal(vector<int>& matchsticks, int stickIndex, vector<int>& 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<int>& 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<int>(;//

        //定义一个数组用于表示正方形的四条边
        vector<int> edgeBox(4;//数组大小为4

        //调用递归函数
        return traversal(matchsticks, 0, edgeBox, matchstickSum / 4;
    }
};

划分k个相等子集

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

示例 1：

输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

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

1 <= k <= len(nums <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内

思路

火柴拼正方形 的抽象版，不同的是，火柴那题本质是求 划分4个相等子集，而本题将需要划分的子集个数拓展到了k个

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

基本思路再过一遍：

​ 2、若数组元素总和能够均分为k个子集，那么就遍历待划分数组元素，不断尝试放入子集数组中（过程使用递归回溯实现）

代码

回溯分析

1、确定回溯函数的参数与返回值

和火柴那题一样，返回值是布尔，参数是：待划分数组nums、待划分数组遍历下标numsIndex，子集数组subBox，子集长度subLen

class Solution {
private://确定递归函数参数和返回值
    bool traversal(vector<int>& nums, int numsIndex, vector<int>& subBox, int subLen{
        
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k {        
    }
};

2、确定终止条件

终止条件也是一样的：当待划分数组遍历下标numsIndex遍历至最后一个元素，就结束。

class Solution {
private://确定递归函数参数和返回值
    bool traversal(vector<int>& nums, int numsIndex, vector<int>& subBox, int subLen{
        //确定终止条件
        if(numsIndex == nums.size( return true;
        
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k {        
    }
};

3、确定单层处理逻辑

这里是重点了，虽然逻辑是可以直接套用火柴那题的，但是需要做一定的剪枝才能ac

什么意思呢？

该剪枝点会在以下情况被触发：

如果下一个位置（例如subBox[3]）所记录的元素总和等于上一个位置（例如subBox[2]）的，那么其实该元素还是放不进，因此就没有必要再去执行下面 "尝试放入数组" 的操作了，可以直接去试subBox的下一个位置，从而提高了性能

第一个待划分数组的遍历值放入subBox时，由于subBox元素均为0，所以放哪个都行，不用再去选择了，直接令其放在第一个，这样又节约了一些开销

class Solution {
private://确定递归函数参数和返回值
    bool traversal(vector<int>& nums, int numsIndex, vector<int>& 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<int>& nums, int k {

    }
};

本质上，此处的剪枝操作都是在递归判断之前，人为的筛选掉一些情况，减少触发递归的次数，进而提升性能

完整代码

class Solution {
private://确定递归函数参数和返回值
    bool traversal(vector<int>& nums, int numsIndex, vector<int>& 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<int>& 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<int>(;

        //创建子集数组
        vector<int> subBox(k;

        return traversal(nums, 0, subBox, subLen;

    }
};

公平发饼干

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

分发的 不公平程度 定义为单个孩子在分发过程中能够获得饼干的最大总数。

示例 1：

输出：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 的分发方案。

输入：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 <= 8
1 <= cookies[i] <= 105
2 <= k <= cookies.length

思路

但是，需要使这些子集之间的差值尽量的小
TBD

声明：本文由用户投稿上传，本站不保证内容的真实与正确性，并且不承担相关法律责任，如有侵权请提供版权资料并联系删除！

编程笔记 » [LeetCode回溯算法#extra01]集合划分问题[火柴拼正方形/划分k个相等子集/公平发饼干]