LC 698. Partition to K Equal Sum Subsets 面试分享

在我看来这是一道med+的题，在intern面试时遇到，知道大约用回溯可以做，但苦于剪枝条件很多没能理清记住，差点放弃了。
LC题解里有很多漂亮的剪枝方法，这里就不赘述了。并且对于我这样新手，没办法一下子完全领会，也就不好记忆。
所以我想说的是，面试遇到这题，也不能轻易放弃，先把不剪枝的框架写出来，再有时间的情况下和面试官一点点followup，增加一些剪枝。

code写的不好，大家勿喷，只是分享一个新手如何在面试中不放弃的精神与策略。谢谢！

//通过测试用例148/159：
class Solution {


    boolean[] used;
    int target;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int max = nums[0];
        for (int num : nums) {
            sum = sum + num;
            max = Math.max(max, num);
        }
        if (sum % k != 0) return false;
        target = sum / k;
        if (max > target) return false;

        used = new boolean[nums.length];

        return dfs(nums, k, 0, 0);

    } // 以上这部分应该还好理解，求出总和/k=target（无法整除false），max大于target（没法分false）。

      // 关键下面回溯不好剪枝，那就先不剪，把最基本框架搭好，就可以通过测试用例148/159了。
    public boolean dfs(int[] nums, int k, int bucket, int idx) {

        if (k == 0) return true;  //所有元素都分好了，true。
        if (idx == nums.length) return false; //元素还没分好，但搜索到数组尾了，false。
        if (bucket == target) {
            return dfs(nums, k-1, 0, 0);
        } //分好了一筐，继续分下一筐。

        //回溯公式1不选择当前元素，进行搜索idx+1。
        if (dfs(nums, k, bucket, idx+1)) return true;

        //回溯公式2选择当前元素，进行搜索idx+1。
        bucket = bucket + nums[idx];
        used[idx] = true;
        if (dfs(nums, k, bucket, idx+1)) return true;
        bucket = bucket - nums[idx];
        used[idx] = false;

        return false;
    }
}

供参考，dp[state]表示state状态下，划分为和均为target的组（最后一组除外）后的余数

1. class Solution {
   
2.     public boolean canPartitionKSubsets(int[] nums, int k) {
   
3.         int n = nums.length;
   
4.         int total = 0;
   
5.         for (int num: nums) {
   
6.             total += num;
   
7.         }
   
8.         int target = total / k;
   
9.         if (total % k != 0) {
   
10.             return false;
    
11.         }
    
12. 
    
13.         Arrays.sort(nums);
    
14.         int size = (1 << n);
    
15.         int[] dp = new int[size];
    
16.         Arrays.fill(dp, -1);
    
17.         dp[0] = 0;
    
18. 
    
19.         for (int prev=0; prev<size; prev++) {
    
20.             if (dp[prev] == -1) {
    
21.                 continue;
    
22.             }
    
23. 
    
24.             for (int j=0; j < n; j++) {
    
25.                 if ((prev & (1 << j)) != 0) {
    
26.                     continue;
    
27.                 }
    
28.                 int nxt = prev | (1 << j);
    
29.                 if (dp[prev] + nums[j] <= target) {
    
30.                     dp[nxt] = (dp[prev] + nums[j]) % target;
    
31.                 } else {
    
32.                     break;
    
33.                 }
    
34.             }
    
35.         }
    
36.         return dp[size-1] == 0;
    
37.     }
    
38. }

复制代码

楼主可以多上中国lc看看不同的解答，这道题数据量不大的话，用状压dp要好写的多

谢谢分享，收获很多