专栏首页glm的全栈学习之路Leetcode 698. 划分为k个相等的子集

Leetcode 698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。

示例 1:

输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出: True 说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。

注意:

1 <= k <= len(nums) <= 16 0 < nums[i] < 10000

算是比较慢的解法吧,先判断数组总和是否是k的倍数,不是就false,然后置一vis数组标记是否访问过,dfs从0到k-1 共k个集合,做完一个做下一个(做完的意思是填正好sum/k的值)

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) 
            sum += nums[i];
        
        if(sum % k != 0 ) return false;
        int avg = sum / k;
        boolean[] flag = new boolean[len];
        return help(nums,flag,avg,k,avg,0);
    }
    
    public static boolean help(int[] nums, boolean[] flag, int avg, int k, int temp, int index ){
 
        if (k == 0 ) return true;
 
        if (temp == 0)
            return help(nums,flag,avg,k-1,avg,0);
 
        for (int i = index; i < nums.length; i++) {
            if (flag[i] == true) continue;
 
            flag[i] = true;
            if(temp-nums[i]>=0 && help(nums,flag,avg,k,temp-nums[i],index+1)){
                return true;
            }
            flag[i] = false;
 
        }
 
        return false;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 过河卒

    P1002 过河卒 题目描述 棋盘上AAA点有一个过河卒,需要走到目标BBB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CCC点有一个对方的马,该马所...

    glm233
  • 排序算法之我观

    笔者今年是xmu大一新生 9月初学编程 学到泡排的时候就对排序这一块深入了解 (也只是很粗浅地学习了一下) 写这篇文章的初衷就是复习一下之前所学,有不足...

    glm233
  • Python Tips(1) 数字与字符串之间转换,采用内置函数

    glm233
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-2 使用函数求奇数和

    其中函数even将根据用户传入的参数n的奇偶性返回相应值:当n为偶数时返回1,否则返回0。函数OddSum负责计算并返回传入的N个整数List[]中所有奇数的和...

    C you again 的博客
  • LeetCode第二天&第三天

    leetcode 第二天 2017年12月27日 4.(118)Pascal's Triangle ? JAVA class Solution { pu...

    郭耀华
  • 一些零碎的小知识点

    小闫同学啊
  • top100习题

    根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    黑白格
  • UESTC 1584 Washi与Sonochi的约定【树状数组裸题+排序】

    题目链接:UESTC 1584 Washi与Sonochi的约定 题意:在二维平面上,某个点的ranked被定义为x坐标不大于其x坐标,且y坐标不大于其y坐标的...

    Angel_Kitty
  • 最大堆,DP问题-LeetCode 373 374 376 377 605(DP,最大堆)

    给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums...

    算法工程师之路
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack

扫码关注云+社区

领取腾讯云代金券