698.Partition-to-K-Equal-Sum-Subsets

698. Partition to K Equal Sum Subsets

题目地址

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

题目描述

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.

代码

Approach #1 DFS

class Solution {
     public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0)        return false;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        return dfs(nums, k, sum / k, 0, 0, visited);
    }

    private boolean dfs(int[] nums, int k, int target, int start, int curSum, boolean[] visited) {
        if (k == 1)        return true;
        if (curSum > target)        return false;
        if (curSum == target)        return dfs(nums, k - 1, target, 0, 0, visited);
        for (int i = start; i < nums.length; i++) {
            if (visited[i])        continue;
            visited[i] = true;
            if (dfs(nums, k, target, i + 1, curSum + nums[i], visited))        return true;
            visited[i] = false;            // 不能少
        }
        return false;
    }
}

Approach #2 DFS + Greedy

class Solution {
  public boolean canPartitionKSubsets(int[] nums, int k) {
    // 1. compute the target sum for each set
        int sum  = Arrays.stream(nums).sum();
    if (sum % k > 0)    return false;
    int target = sum / k;
    // 2. sort
    Arrays.sort(nums);
    // 3. 从大到小prune等于target的elements
    int row = nums.length - 1;
    if (nums[row] > target) return false;
    while (row >= 0 && nums[row] == target) {
      row--;
      k--;
    }

    return search(new int[k], row, nums, target);
  }

  private boolean search(int[] groups, int row, int[] nums, int target) {
    if (row < 0)        return true;
    int v = nums[row];
    for (int i = 0; i < groups.length; i++) {
      if (groups[i] + v <= target) {
        groups[i] += v;
        if (search(groups, row - 1, nums, target))    return true;
        groups[i] -= v;
      }
      if (groups[i] == 0)     break; // in the first run of search, we will make only 1 recursive call, instead of k
    }
    return false;
  }

}

Approach #3 Dynamic Programming Confusion

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int N = nums.length;
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        int target = sum / k;
        if (sum % k > 0 || nums[N - 1] > target) return false;

        boolean[] dp = new boolean[1 << N];
        dp[0] = true;
        int[] total = new int[1 << N];

        for (int state = 0; state < (1 << N); state++) {
            if (!dp[state]) continue;
            for (int i = 0; i < N; i++) {
                int future = state | (1 << i); // 把state的第 i 位置为 1
                if (state != future && !dp[future]) {
                    if (nums[i] <= target - (total[state] % target)) {
                        dp[future] = true;
                        total[future] = total[state] + nums[i];
                    } else {
                        break;
                    }
                }
            }
        }
        return dp[(1 << N) - 1];
    }
}

Approach #4 TLE

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;    
        Arrays.sort(nums);  
        return dfs(nums, sum / k, 0, k, 0);
    }

    private boolean dfs(int[] nums, int target, int cur, int k, int used) {
        if (k == 0) return used == (1 << nums.length) - 1;
        for (int i = 0; i < nums.length; ++i) {
            if ((used & (1 << i)) == 1) continue;
            int t = cur + nums[i];
            if (t > target) break; // Important
            int new_used = used | (1 << i);
            if (t == target && dfs(nums, target, 0, k - 1, new_used)) {
        return true; 
      } else if (dfs(nums, target, t, k, new_used)){
         return true;
      }
        }
        return false;
    }  
};