专栏首页机器学习入门LWC 54:698. Partition to K Equal Sum Subsets

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 条评论
登录 后参与评论

相关文章

  • 算法细节系列(27):时间复杂度为何还能优化?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Largest Number Greater Than Twice of Others

    思路1: 非排序,如果存在一个数,比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)

    用户1147447
  • 算法细节系列(21):贪心有理?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • leetcode 26 Remove Duplicates from Sorted Array

    Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 2127...

    流川疯
  • 算法细节系列(27):时间复杂度为何还能优化?

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • Leetcode 41 First Missing Positive 正解不是盛传的桶排序

    Given an unsorted integer array, find the first missing positive integer. For ...

    triplebee
  • LeetCode第53题

    Given an integer array nums, find the contiguous subarray (containing at least o...

    用户3112896

扫码关注云+社区

领取腾讯云代金券