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;
  }
  }