[LeetCode] 698. Partition to K Equal Sum Subsets

kuangcaibao 发布于2019-08-16 13:41 / 3422人阅读

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.

Solution

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num: nums) sum += num;
        if (k == 0 || sum%k != 0 || sum < k) return false;
        int target = sum/k;
        return dfs(nums, new boolean[nums.length], 0, k, 0, target);
    }
    private boolean dfs(int[] nums, boolean[] used, int start, int k, int sum, int target) {
        if (k == 1) return true;
        if (sum == target) return dfs(nums, used, 0, k-1, 0, target);
        for (int i = start; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                if (dfs(nums, used, i+1, k, sum+nums[i], target)) return true;
                used[i] = false;
            }
        }
        return false;
    }
}

GPU云服务器云服务器 equal Subsets LeetCode Partition

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72173.html

leetcode416. Partition Equal Subset Sum

摘要：题目要求假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。而这里的问题等价于，有个物品，每个物品承重为，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。题目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

Caicloud 2019-08-16 15:10 评论0 收藏0
[Leetcode - Dynamic Programming] Partition Equal S

摘要：背包问题假设有个宝石，只有一个容量为的背包，且第个宝石所对应的重量和价值为和求装哪些宝石可以获得最大的价值收益思路我们将个宝石进行编号，寻找的状态和状态转移方程。我们用表示将前个宝石装到剩余容量为的背包中，那么久很容易得到状态转移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

qpal 2019-08-14 16:41 评论0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 评论0 收藏0
leetcode 416 Partition Equal Subset Sum

摘要：如果是奇数的话，那一定是不满足条件的，可以直接返回。如果是偶数，将除获得我们要求的一个子数组元素的和。如何暂存我们计算的中间结果呢声明一个长度为的布尔值数组。每个元素的布尔值代表着，数组中是否存在满足加和为的元素序列。题目详情 Given a non-empty array containing only positive integers, find if the array ca...

jsummer 2019-08-16 11:07 评论0 收藏0
[LeetCode] 663. Equal Tree Partition

Problem Given a binary tree with n nodes, your task is to check if its possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tr...

coordinate35 2019-08-16 13:48 评论0 收藏0