[LeetCode] 416. Partition Equal Subset Sum

makeFoxPlay 发布于2019-08-16 13:42 / 3420人阅读

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 element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Solution DFS1

class Solution {
    public boolean canPartition(int[] nums) {
        Map map = new HashMap<>();
        int sum = 0;
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
            sum += num;
        }
        if (sum % 2 != 0) return false;
        return dfs(map, sum/2);
    }
    private boolean dfs(Map map, int target) {
        if (map.containsKey(target) && map.get(target) > 0) return true;
        for (int num: map.keySet()) {
            if (num < target && map.get(num) > 0) {
                map.put(num, map.get(num)-1);
                if (dfs(map, target-num)) return true;
                map.put(num, map.get(num)+1);
            }
        }
        return false;
    }
}

DFS2 - TLE

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

TLE for this test case:
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

专线服务服务器托管 Subset equal mvc416 LeetCode

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

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

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
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 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] 698. Partition to K Equal Sum Subsets

Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...

kuangcaibao 2019-08-16 13:41 评论0 收藏0