資訊專欄INFORMATION COLUMN
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]
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72189.html
摘要：如果是奇數(shù)的話，那一定是不滿足條件的，可以直接返回。如果是偶數(shù)，將除獲得我們要求的一個(gè)子數(shù)組元素的和。如何暫存我們計(jì)算的中間結(jié)果呢聲明一個(gè)長度為的布爾值數(shù)組。每個(gè)元素的布爾值代表著，數(shù)組中是否存在滿足加和為的元素序列。 題目詳情 Given a non-empty array containing only positive integers, find if the array ca...
摘要：題目要求假設(shè)有一個(gè)全為正整數(shù)的非空數(shù)組，將其中的數(shù)字分為兩部分，確保兩部分?jǐn)?shù)字的和相等。而這里的問題等價(jià)于，有個(gè)物品，每個(gè)物品承重為，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。 題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...
摘要：背包問題假設(shè)有個(gè)寶石，只有一個(gè)容量為的背包，且第個(gè)寶石所對應(yīng)的重量和價(jià)值為和求裝哪些寶石可以獲得最大的價(jià)值收益思路我們將個(gè)寶石進(jìn)行編號(hào)，尋找的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。我們用表示將前個(gè)寶石裝到剩余容量為的背包中，那么久很容易得到狀態(tài)轉(zhuǎn)移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...
摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
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,...
閱讀 3724·2021-10-12 10:11
閱讀 1992·2019-08-30 15:53
閱讀 1599·2019-08-30 13:15
閱讀 2312·2019-08-30 11:25
閱讀 1809·2019-08-29 11:24
閱讀 1657·2019-08-26 13:53
閱讀 3530·2019-08-26 13:22
閱讀 1773·2019-08-26 10:24
