• 698. 划分为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)等于总和。
    
    • 1
    • 2
    • 3
    示例 2:
    输入: nums = [1,2,3,4], k = 3
    输出: false
    
    • 1
    • 2
    提示:
    1 <= k <= len(nums) <= 16
    0 < nums[i] < 10000
    每个元素的频率在 [1,4] 范围内
    
    • 1
    • 2
    • 3

    解题思路 暴力DFS+剪枝

    首先计算总和sum,若总和无法除尽k,则说明分配一定失败。
    每个子集总和为goal = sum/k
    dfs

    • 整个dfs需要16层,每个节点16个分支,即选择一个nums的排列方式可以完成从上到小累加依次填充k个子集,其总和goal相同
    • dfs每一层尝试对当前子集从数组中选择一个数进行填充
    • 已使用的跳过,超过子集的和跳过
    • 若子集可以容纳下该数,继续dfs
    • 若子集容纳该数后达到goal,则进入下一个子集进行填充

    剪枝
    如此的dfs一定是爆炸的,接下来进行剪枝,有两个剪枝原则:

    • 实现对nums进行排序,遍历下一层的数时,选择比当前数小的点,因为从大到小的遍历方式使得当前子集不可能容纳比当前数更大的(注意重新开始一个子集需要从最大的数开始遍历)
    • 子集是新的才进入,此时若最大的元素无法装入,那么一定不成立(如8要装入容量为5的所有子集是不可能的)

    代码

    class Solution {
    public:
        bool dfs(int idx, vector<int>& nums, vector<bool>& mark, int goal, int sum,int k){
            /* 
            * idx: 当前尝试添加数组中的idx位置元素
            * nums: 输入整数组
            * mark: 标记每一个位置整数是否被使用
            * goal: 每个子集的总和
            * sum: 当前子集的总和,达到即可进入下一个子集
            * k: 当前剩余的待填满的子集个数
            * dfs递归剪枝:dfs每一层尝试对当前子集填充每个数(已使用的跳过,超过子集的和跳过),
            *               若子集可以容纳下该数,继续dfs;若子集容纳该数后达到goal,则进入下一个子集进行填充
            *               注意剪枝策略:
            *               ①遍历下一层的数时,选择比当前数小的点(事先排序则从idx+1开始遍历),
            *               重新开始一个子集需要从最大的数开始遍历
            *               ②子集才开始装元素,此时若最大的元素无法装入,那么一定容纳不下该元素,如8要装入容量为5的所有子集
            */
            cout<<idx<<" "<<sum<<" "<<k<<endl;
            if(k == 0) return true; // 所有子集填满了
            if(goal == sum) return dfs(0, nums, mark, goal, 0, --k ); // 填满一个子集,进入下一个子集
            for(int i = idx; i<nums.size(); i++){
                if(mark[i]) continue; // 已使用此点
                if(sum + nums[i] > goal) continue; // 超过子集的容量
                mark[i] = true;
                if(dfs(i+1, nums, mark, goal, sum+nums[i], k)) return true; // 将i放入集合中,注意下一个点从(i+1)开始,因为这个集合不可能容纳比nums[i]还大的元素了(nums提前排序了的)
                mark[i] = false; // 回溯
                if(sum == 0) return false; // sum==0表示此子集才开始装元素,此时若最大的元素无法装入,那么一定容纳不下该元素,如8要装入容量为5的所有子集
            }
            return false;
        } 
    
        bool canPartitionKSubsets(vector<int>& nums, int k) {
            int sum = 0;
            for(int i = 0; i < nums.size(); i++) sum += nums[i];
            if(sum%k) return false; // 不可除清说明一定分配不均匀
    
            vector<bool> mark(nums.size(), 0); // 标记是否使用
            sort(nums.begin(), nums.end(), greater<int>()); // 排序使得每次访问可以更优
            return dfs(0, nums, mark, sum/k, 0, k);
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
  • 相关阅读:
    8-15外部排序-最佳归并树
    关于 SAP Spartacus 重定向部分外部 url 到后台系统的问题
    Delphi 打包文件到APK安装包中
    基于STM32的智能小车app自学梳理(一)
    【leetcode 力扣刷题】栈—波兰式///逆波兰式相关知识和题目
    Python--逻辑运算符(与或非) and or not
    C++ map和unordered_map的区别和联系以及map的使用
    java毕业设计宠物之家电子商务网站mybatis+源码+调试部署+系统+数据库+lw
    windows编译ZLMediaKit流媒体服务webrtc
    锁的概念!
  • 原文地址:https://blog.csdn.net/weixin_44639164/article/details/126977372