This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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 = 4Output:TrueExplanation: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`

.b'

\n#### Approach #1: Search by Constructing Subset Sums [Accepted]

\n\n\n

\n#### Approach #2: Dynamic Programming on Subsets of Input [Accepted]

\n\n\n\n\n

\n

'
\n\n

\n**Intuition**

As even when `k = 2`

, the problem is a "Subset Sum" problem which is known to be NP-hard, (and because the given input limits are low,) our solution will focus on exhaustive search.

A natural approach is to simulate the `k`

groups (disjoint subsets of nums). For each number in `nums`

, we\'ll check whether putting it in the `i`

-th group solves the problem. We can check those possibilities by recursively searching.

**Algorithm**

Firstly, we know that each of the `k`

group-sums must be equal to `target = sum(nums) / k`

. (If this quantity is not an integer, the task is impossible.)

For each number in `nums`

, we could add it into one of `k`

group-sums, as long as the group\'s sum would not exceed the `target`

. For each of these choices, we recursively search with one less number to consider in `nums`

. If we placed every number successfully, then our search was successful.

One important speedup is that we can ensure all the 0 values of each group occur at the end of the array `groups`

, by enforcing `if (groups[i] == 0) break;`

. This greatly reduces repeated work - for example, in the first run of search, we will make only 1 recursive call, instead of `k`

. Actually, we could do better by skipping any repeated values of groups[i], but it isn\'t necessary.

Another speedup is we could sort the array `nums`

, so that we try to place the largest elements first. When the answer is true and involves subsets with a low size, this method of placing elements will consider these lower size subsets sooner. We can also handle elements `nums[i] >= target`

appropriately. These tricks are not necessary to solve the problem, but they are presented in the solutions below.

**Python**

class Solution(object):\n def canPartitionKSubsets(self, nums, k):\n target, rem = divmod(sum(nums), k)\n if rem: return False\n\n def search(groups):\n if not nums: return True\n v = nums.pop()\n for i, group in enumerate(groups):\n if group + v <= target:\n groups[i] += v\n if search(groups): return True\n groups[i] -= v\n if not group: break\n nums.append(v)\n return False\n\n nums.sort()\n if nums[-1] > target: return False\n while nums and nums[-1] == target:\n nums.pop()\n k -= 1\n\n return search([0] * k)\n

**Java**

class Solution {\n public boolean search(int[] groups, int row, int[] nums, int target) {\n if (row < 0) return true;\n int v = nums[row--];\n for (int i = 0; i < groups.length; i++) {\n if (groups[i] + v <= target) {\n groups[i] += v;\n if (search(groups, row, nums, target)) return true;\n groups[i] -= v;\n }\n if (groups[i] == 0) break;\n }\n return false;\n }\n\n public boolean canPartitionKSubsets(int[] nums, int k) {\n int sum = Arrays.stream(nums).sum();\n if (sum % k > 0) return false;\n int target = sum / k;\n\n Arrays.sort(nums);\n int row = nums.length - 1;\n if (nums[row] > target) return false;\n while (row >= 0 && nums[row] == target) {\n row--;\n k--;\n }\n return search(new int[k], row, nums, target);\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`nums`

, and is as given. As we skip additional zeroes in`groups`

, naively we will make calls to`search`

, then an additional calls after every element of`groups`

is nonzero. \n - \n
Space Complexity: , the space used by recursive calls to

\n`search`

in our call stack. \n

\n

**Intuition and Algorithm**

As in *Approach #1*, we investigate methods of exhaustive search, and find `target = sum(nums) / k`

in the same way.

Let `used`

have the `i`

-th bit set if and only if `nums[i]`

has already been used. Our goal is to use `nums`

in some order so that placing them into groups in that order will be valid. `search(used, ...)`

will answer the question: can we partition unused elements of `nums[i]`

appropriately?

This will depend on `todo`

, the sum of the remaining unused elements, not crossing multiples of `target`

within one number. If for example our target is `10`

, and our elements to be placed in order are `[6, 5, 5, 4]`

, this would not work as `6 + 5`

"crosses" `10`

prematurely.

If we could choose the order, then after placing `5`

, our unused elements are `[4, 5, 6]`

. Using `6`

would make `todo`

go from `15`

to `9`

, which crosses `10`

- something unwanted. However, we could use `5`

since `todo`

goes from `15`

to `10`

; then later we could use `4`

and `6`

as those placements do not cross.

It turns out the maximum value that can be chosen so as to not cross a multiple of `target`

, is `targ = (todo - 1) % target + 1`

. This is essentially `todo % target`

, plus `target`

if that would be zero.

Now for each unused number that doesn\'t cross, we\'ll search on that state, and we\'ll return `true`

if any of those searches are `true`

.

Notice that the state `todo`

depends only on the state `used`

, so when memoizing our search, we only need to make lookups by `used`

.

In the solutions below, we present both a top-down dynamic programming solution, and a bottom-up one. The bottom-up solution uses a different notion of state.

\n**Python**

class Solution(object):\n def canPartitionKSubsets(self, nums, k):\n target, rem = divmod(sum(nums), k)\n if rem or max(nums) > target: return False\n\n memo = [None] * (1 << len(nums))\n memo[-1] = True\n def search(used, todo):\n if memo[used] is None:\n targ = (todo - 1) % target + 1\n memo[used] = any(search(used | (1<<i), todo - num)\n for i, num in enumerate(nums)\n if (used >> i) & 1 == 0 and num <= targ)\n return memo[used]\n\n return search(0, target * k)\n

**Java**

enum Result { TRUE, FALSE }\n\nclass Solution {\n boolean search(int used, int todo, Result[] memo, int[] nums, int target) {\n if (memo[used] == null) {\n memo[used] = Result.FALSE;\n int targ = (todo - 1) % target + 1;\n for (int i = 0; i < nums.length; i++) {\n if ((((used >> i) & 1) == 0) && nums[i] <= targ) {\n if (search(used | (1<<i), todo - nums[i], memo, nums, target)) {\n memo[used] = Result.TRUE;\n break;\n }\n }\n }\n }\n return memo[used] == Result.TRUE;\n }\n public boolean canPartitionKSubsets(int[] nums, int k) {\n int sum = Arrays.stream(nums).sum();\n if (sum % k > 0) return false;\n\n Result[] memo = new Result[1 << nums.length];\n memo[(1 << nums.length) - 1] = Result.TRUE;\n return search(0, sum, memo, nums, sum / k);\n }\n}\n

*Bottom-Up Variation*

**Python**

class Solution(object):\n def canPartitionKSubsets(self, nums, k):\n nums.sort()\n target, rem = divmod(sum(nums), k)\n if rem or nums[-1] > target: return False\n\n dp = [False] * (1 << len(nums))\n dp[0] = True\n total = [0] * (1 << len(nums))\n\n for state in xrange(1 << len(nums)):\n if not dp[state]: continue\n for i, num in enumerate(nums):\n future = state | (1 << i)\n if state != future and not dp[future]:\n if (num <= target - (total[state] % target)):\n dp[future] = True\n total[future] = total[state] + num\n else:\n break\n return dp[-1]\n

**Java**

class Solution {\n public boolean canPartitionKSubsets(int[] nums, int k) {\n int N = nums.length;\n Arrays.sort(nums);\n int sum = Arrays.stream(nums).sum();\n int target = sum / k;\n if (sum % k > 0 || nums[N - 1] > target) return false;\n\n boolean[] dp = new boolean[1 << N];\n dp[0] = true;\n int[] total = new int[1 << N];\n\n for (int state = 0; state < (1 << N); state++) {\n if (!dp[state]) continue;\n for (int i = 0; i < N; i++) {\n int future = state | (1 << i);\n if (state != future && !dp[future]) {\n if (nums[i] <= target - (total[state] % target)) {\n dp[future] = true;\n total[future] = total[state] + nums[i];\n } else {\n break;\n }\n }\n }\n }\n return dp[(1 << N) - 1];\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`nums`

. There are states of`used`

(or`state`

in our bottom-up variant), and each state performs`O(N)`

work searching through`nums`

. \n - \n
Space Complexity: , the space used by

\n`memo`

(or`dp`

,`total`

in our bottom-up variant). \n

\n

Analysis written by: @awice.

\n