首页 > 编程语言 >回溯算法:集合划分问题

回溯算法:集合划分问题

时间:2022-09-21 21:00:11浏览次数:97  
标签:index return nums int sum matchsticks 算法 回溯 集合

框架

回溯算法中需要考虑到的问题

  • 路径,选择列表,结束条件

结束条件

// 结束条件:已经处理完所有数
if (track.size() == nums.length) {
    // 处理逻辑
}
// 结束条件:已经处理完所有球
if (index == nums.length) {
    // 处理逻辑
}

划分为k个相等的字串

class Solution {
public:

    bool dfs(vector<int>& nums, int index, vector<int>& v, int target){
        if(index == nums.size()){
            return true;
        }
        for(int i = 0; i < v.size(); ++i){
            //若不进行此步优化,则超时
            if(i && v[i] == v[i - 1]){
                continue;
            }
            v[i] += nums[index];
            if(v[i] <= target && dfs(nums, index + 1, v, target)){
                return true;
            }
            v[i] -= nums[index];
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0){
            return false;
        }

        sort(nums.begin(), nums.end(), greater<int>());
        vector<int> v(k);
        return dfs(nums, 0 , v, sum / k);
    }
};

火柴拼正方形

class Solution {
public:
    bool dfs(int index, vector<int>& matchsticks, vector<int>& edges, int len){

        if(index == matchsticks.size()){
            return true;
        }
        for(int i = 0; i < edges.size(); i++){
            edges[i] += matchsticks[index];
            if(edges[i] <= len && dfs(index + 1, matchsticks, edges, len)){
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }

    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if(sum % 4 != 0){
            return false;
        }
        //降序排序
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        vector<int> edges(4);
        return dfs(0, matchsticks, edges, sum / 4);
    }
};

公平分发饼干

标签:index,return,nums,int,sum,matchsticks,算法,回溯,集合
From: https://www.cnblogs.com/changebaobao/p/16712632.html

相关文章

  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素
    2022/09/21第一天数组第一题第二题思路:交换数值为val的元素与最后一个元素的位置,并减少数组的长度......
  • AcWing 算法提高课 欧拉回路和欧拉路径
    定义:经过每一条边且每一条边恰好只经过一次一、无向图中,当所有边都连通时:存在欧拉路径,等价于,图中度为奇数的点只有0或2个。存在欧拉回路,等价于,图中度为奇数的点只有0个......
  • 集合
    是对象的容器,实现了对对像的常用操作,类似于数组的功能。数组长度固定,集合长度部固定。数组可以存储基本类型和引用类型,集合只能存储引用类型。Collection体系集合colle......
  • 04-基于锚框的额单阶段检测算法:SSD
                                     ......
  • MD5算法工具类
    importjava.security.MessageDigest;importjava.security.NoSuchAlgorithmException;/***MD5算法工具类*@authorXLINK**/publicclassMD5Tool{/......
  • PID控制算法
    闭环控制(反馈回路closeloop):  闭环控制系统需要目标量,执行器,传感器通过偏差量获得执行量是最为重要的目标量和传感器获得的执行器数据都需要是连续的;偏差量来自于......
  • 排序算法基本思想及实现
    一、插入排序1、直接插入排序基本思想:类似抓扑克牌,待排序元素在已排序的序列中从后往前遍历,遇到小于他的元素向后移一位,直至遇到小于或等于他的元素,在其后插入即......
  • 排序算法动画演示
    本文由简悦SimpRead转码,原文地址blog.csdn.net一、直接插入排序(StraightInsertionSorting)把新的数据插入到已经排好的数据列中。将第一个数和第二个数排序,......
  • 算法-动态规划(DP)
     时间:2022/09/21 一.引入-斐波那契数列下图展示了斐波那契数列数列的递归式:然后我们再看一下在计算fib(7)的时候会出现什么问题:如上图所示,在计算fib(7)的时候......
  • Problem P14. [算法课动态规划]连续数组最大和
    感觉很简单的一道题,curnum存下连续数组和大于0的数值,maxnum存下最大连续数组和,curnum从数组头开始,遍历数组,+=数组值,当curnum大于0时,那么即便紧接着的后面有一个很大的......