LWC 54:698. Partition to K Equal Sum Subsets

LWC 54:698. Partition to K Equal Sum Subsets

传送门:698. Partition to K Equal Sum Subsets

Problem:

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.

0 < nums[i] < 10000.

思路: 观察 k 和 n 发现均很小,所以实际上是暴力dfs算法,先预处理,如果sum / k 有余数,则不能分割。接着nums中的每个元素对应k个状态,所有有n^k中情况,dfs用到了剪枝,排序贪心尽早把不合法的解从递归树中删除。

代码如下:

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int max = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        if (sum % k != 0) return false;
        tar = sum / k;
        if (max > tar) return false;
        Arrays.sort(nums);
        return go(nums, n - 1, k, new int[k]);
    }

    int tar = 0;
    boolean go(int[] nums, int pos, int k, int[] sums) {
        if (pos == -1) {
            boolean check = true;
            for (int i = 0; i < k; ++i) {
                if (sums[i] != tar) check = false;
            }
            return check;
        }
        for (int i = 0; i < k; ++i) {
            sums[i] += nums[pos];
            if (sums[i] <= tar && go(nums, pos - 1, k, sums)) {
                return true;
            }
            sums[i] -= nums[pos];
        }
        return false;
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 15 3Sum + 有趣的小BUG

Given an array S of n integers, are there elements a, b, c in S such that a + b...

1766
来自专栏Code_iOS

数据结构:栈与队列

工程代码 Github: Data_Structures_C_Implemention -- Stack & Queue

823
来自专栏King_3的技术专栏

leetcode-633-Sum of Square Numbers

1082
来自专栏cmazxiaoma的架构师之路

Java数据结构与算法(3) 寻找中序遍历时的下一个结点

1043
来自专栏尾尾部落

[剑指offer] 斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39

522
来自专栏恰同学骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

682
来自专栏恰同学骚年

剑指Offer面试题:30.第一个只出现一次的字符

  最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字...

592
来自专栏恰同学骚年

数据结构基础温故-3.队列

在日常生活中,队列的例子比比皆是,例如在车展排队买票,排在队头的处理完离开,后来的必须在队尾排队等候。在程序设计中,队列也有着广泛的应用,例如计算机的任务调度系...

671
来自专栏恰同学骚年

数据结构基础温故-6.查找(上):基本查找与树表查找

只要你打开电脑,就会涉及到查找技术。如炒股软件中查股票信息、硬盘文件中找照片、在光盘中搜DVD,甚至玩游戏时在内存中查找攻击力、魅力值等数据修改用来作弊等,都要...

853
来自专栏机器学习入门

LWC 53:691. Stickers to Spell Word

LWC 53:691. Stickers to Spell Word 传送门:691. Stickers to Spell Word Problem: We ...

3005

扫码关注云+社区