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.
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; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/72173.html
摘要:題目要求假設(shè)有一個(gè)全為正整數(shù)的非空數(shù)組,將其中的數(shù)字分為兩部分,確保兩部分?jǐn)?shù)字的和相等。而這里的問(wèn)題等價(jià)于,有個(gè)物品,每個(gè)物品承重為,問(wèn)如何挑選物品,使得背包的承重搞好為所有物品重量和的一般。 題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...
摘要:背包問(wèn)題假設(shè)有個(gè)寶石,只有一個(gè)容量為的背包,且第個(gè)寶石所對(duì)應(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...
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 ...
摘要:如果是奇數(shù)的話,那一定是不滿足條件的,可以直接返回。如果是偶數(shù),將除獲得我們要求的一個(gè)子數(shù)組元素的和。如何暫存我們計(jì)算的中間結(jié)果呢聲明一個(gè)長(zhǎng)度為的布爾值數(shù)組。每個(gè)元素的布爾值代表著,數(shù)組中是否存在滿足加和為的元素序列。 題目詳情 Given a non-empty array containing only positive integers, find if the array ca...
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...
閱讀 1784·2023-04-25 15:51
閱讀 2497·2021-10-13 09:40
閱讀 2134·2021-09-23 11:22
閱讀 3244·2019-08-30 14:16
閱讀 2652·2019-08-26 13:35
閱讀 1847·2019-08-26 13:31
閱讀 874·2019-08-26 11:39
閱讀 2732·2019-08-26 10:33