698. Partition to K Equal Sum Subsets.md

698. Partition to K Equal Sum Subsets

Question

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.

Solution

• Method 1: dfs + pruning AC slow

   class Solution {
   	public boolean canPartitionKSubsets(int[] nums, int k) {
   		if(nums == null || nums.length < 4) return false;
   		int sum = 0;
   		for(int num : nums) sum += num;
   		if(sum % k != 0) return false;
   		return dfs(nums, 0, k, 0, sum / k, new boolean[nums.length]);
   	}
   	private boolean dfs(int[] nums, int count, int k, int cur, int sum, boolean[] visited){
   		if(cur == sum){
   			if(++count == k) return true;
   			else{
   				return dfs(nums, count, k, 0, sum, visited);
   			}
   		}else if(cur < sum){
   			for(int i = 0; i < nums.length; i++){
   				if(visited[i]) continue;
   				visited[i] = true;
   				if(dfs(nums, count, k, cur + nums[i], sum, visited)) return true;
   				visited[i] = false;
   			}
   		}
   		return false;
   	}
   }

• Method 2: dfs: pruning(A better version, beats 97%)

  • use a start index to record the next value to used. For a single value, in each iteration, it will be only used once.
  • once we reach the target, we need to set start back to 0 so dfs has a chance to check all values again.

   class Solution {
   	public boolean canPartitionKSubsets(int[] nums, int k) {
   		if(nums == null || nums.length < k) return false;
   		int sum = 0, max = Integer.MIN_VALUE;
   		for(int num : nums){
   			sum += num; 
   			max = Math.max(max, num);
   		} 
   		if(sum % k != 0 || max > sum / k) return false;
   		sum /= k;
   		return k == 1 || dfs(nums, 0, k, 0, sum, new boolean[nums.length], 0);
   	}
   	private boolean dfs(int[] nums, int count, int k, int cur, int sum, boolean[] visited, int start){
   		if(cur == sum){
   			if(++count == k - 1) return true;
   			else{
   				return dfs(nums, count, k, 0, sum, visited, 0);
   			}
   		}else if(cur < sum){
   			for(int i = start; i < nums.length; i++){
   				if(visited[i]) continue;
   				visited[i] = true;
   				if(dfs(nums, count, k, cur + nums[i], sum, visited, i + 1)) return true;
   				visited[i] = false;
   			}
   		}
   		return false;
   	}
   }