LeetCode 698. Partition to K Equal Sum Subsets

原题链接在这里:https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

题目:

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.

题解:

首先计算sum, 看sum能否被k整除. 若不能, 铁定不能分成k组. return false.

若能的话,每组的target sum就该是sum/k. 一组一组的减掉. 直到 k = 1. 剩下最后一组, 最后一组的sum肯定是sum/k.

因为这里的已经验证过sum是k的倍数, 而前面已经有k-1组 sum/k找到了. 所以可以直接return true.

This is bottom-up recursion. Set parameters for state first.

It needs count to count number in subarray. Since there may be negative number in nums. If target is 0, there could be [-1, 1] or empty subarray. 

The reason state has both visited and cur starting index is because of trimming dfs tree.

When summing up to target, if index i can't be used, when trying j > i, the next level of DFS, there is no need to try i again. Because if i works, it would be added into res before.

The only case i could be used is to sum up next target.

Note: the question is asking for non-empty, we need to add a count of each sub set. And make sure it is > 0 before accumlating to result.

Time Complexity: exponential.

Space: O(n). stack space.

AC Java:

 1 class Solution {
 2     public boolean canPartitionKSubsets(int[] nums, int k) {
 3         if(nums == null || nums.length == 0){
 4             return false;
 5         }
 6         
 7         int sum = 0;
 8         for(int num : nums){
 9             sum += num;
10         }
11         
12         if(sum % k != 0){
13             return false;
14         }
15         
16         boolean [] visited = new boolean[nums.length];
17         return dfs(nums, visited, 0, 0, sum/k, 0, k);
18     }
19     
20     private boolean dfs(int [] nums, boolean [] visited, int cur, int sum, int target, int count, int k){
21         if(sum > target){
22             return false;
23         }
24         
25         if(k == 1){
26             return true;
27         }
28         
29         if(sum == target && count > 0){
30             return dfs(nums, visited, 0, 0, target, 0, k-1);
31         }
32         
33         for(int i = cur; i<nums.length; i++){
34             if(!visited[i]){
35                 visited[i] = true;
36                 if(dfs(nums, visited, i+1, sum+nums[i], target, count++, k)){
37                     return true;
38                 }
39                 
40                 visited[i] = false;
41             }
42         }
43         
44         return false;
45     }
46 }

类似Partition Equal Subset SumMatchsticks to Square.

原文地址:https://www.cnblogs.com/Dylan-Java-NYC/p/7878870.html