回溯 + 剪枝

473.火柴拼正方形

  1. class Solution {
  2.     int t;
  3.     public boolean makesquare(int[] matchsticks) {
  4.         int s = Arrays.stream(matchsticks).sum();
  5.         if (s % 4 != 0 || matchsticks.length < 4) return false;
  6.         t = s / 4;
  7.         Arrays.sort(matchsticks);
  8.         return dfs(matchsticks, 0, 0, 0, matchsticks.length - 1);
  9.     }
  11.     boolean dfs(int[] a, int c, int s, int st, int u) {
  12.         if (c == 4) return true;
  13.         if (s == t) return dfs(a, c + 1, 0, st, a.length - 1);
  15.         for (int i = u; i >= 0; i--) {
  16.             if ((st >> i & 1) == 1 || a[i] + s > t) continue;
  17.             if (dfs(a, c, s + a[i], st | 1 << i, u - 1))
  18.                 return true;
  19.             if (s == 0 || s + a[i] == t) return false;
  20.             while (i > 0 && a[i - 1] == a[i])
  21.                 i--;
  22.         }
  23.         return false;
  24.     }
  25. }

698.划分为k个相等的子集
思路：
方法1：
同473
枚举每个子集选哪些物品
优化1：按物品从大到小枚举
优化2：枚举同一子集时，使用组合而不是排列，因为顺序对结果并没有影响
优化3：如果将一个物品放在子集的开头都无法得到答案，说明无最终答案
优化4：如果一个物品放在一个子集的最后无法得到答案，说明无最终答案（这一点由枚举顺序决定）
优化5：dfs的参数尽可能的少，能放全局的就放全局

  1. class Solution {
  2.     int sum, k;
  3.     int[] a;
  4.     public boolean canPartitionKSubsets(int[] nums, int k) {
  5.         for (int i = 0; i < nums.length; i++)
  6.             sum += nums[i];
  7.         if (sum % k != 0)
  8.             return false;
  9.         sum /= k;
  10.         Arrays.sort(nums);
  11.         reverse(nums);
  13.         a = nums;
  14.         this.k = k;
  15.         return dfs(0, 0, 0, 0);
  16.     }
  17.     boolean dfs(int u, int val, int start, int st) {
  18.         if (u == k)
  19.             return true;
  20.         if (val == sum)
  21.             return dfs(u + 1, 0, 0, st);
  23.         for (int i = start; i < a.length; i++) {
  24.             if ((st >> i & 1) == 1 || val + a[i] > sum)
  25.                 continue;
  26.             if (dfs(u, val + a[i], i + 1, st | (1 << i)))
  27.                 return true;
  28.             while (i + 1 < a.length && a[i] == a[i + 1])
  29.                 i++;
  30.             if (val == 0)
  31.                 return false;
  32.             if (val + a[i] == sum)
  33.                 return false;
  34.         }
  35.         return false;
  36.     }
  37.     void reverse(int[] nums) {
  38.         int l = 0, r = nums.length - 1;
  39.         while (l < r) {
  40.             int t = nums[l];
  41.             nums[l] = nums[r];
  42.             nums[r] = t;
  44.             l++;
  45.             r--;
  46.         }
  47.     }
  48. }

方法2：
枚举每个物品放在哪个子集
优化1：从大到小枚举
优化2：每一层如果已经枚举过相同大小的子集，跳过即可
优化3：如果一个物品放在一个空集中都不能得到最终分类，说明无解
优化4：如果一个物品放在一个子集中恰好为目标大小但仍无法完成最终分类，说明无解

  1. class Solution {
  2.     int n, k;
  3.     int[] nums;
  4.     int[] sum;
  5.     public boolean canPartitionKSubsets(int[] nums, int k) {
  6.         int s = 0;
  7.         for (int x : nums) {
  8.             s += x;   
  9.         }
  10.         if (nums.length < k || s % k != 0)
  11.             return false;
  12.         this.n = nums.length;
  13.         this.k = k;
  14.         this.nums = nums;
  15.         this.sum = new int[k];
  17.         Arrays.sort(nums);
  18.         return dfs(nums.length - 1, s / k);
  19.     }
  21.     boolean dfs(int u, int t) {
  22.         if (u < 0)
  23.             return true;
  25.         Set<Integer> used = new HashSet<>();
  26.         for (int i = 0; i < k; i++) {
  27.             if (nums[u] + sum[i] > t || used.contains(sum[i]))
  28.                 continue;
  29.             used.add(sum[i]);
  31.             sum[i] += nums[u];
  32.             if (dfs(u - 1, t))
  33.                 return true;
  34.             sum[i] -= nums[u];
  36.             if (sum[i] == 0 || nums[u] + sum[i] == t)
  37.                 break;
  38.         }
  39.         return false;
  40.     }
  41. }

1723.完成所有工作的最短时间
思路：
二分 + 枚举每个工作由哪个工人完成

  1. class Solution {
  2.     int[] jobs;
  3.     int n, k;
  4.     int[] sum;
  5.     public int minimumTimeRequired(int[] jobs, int k) {
  6.         this.n = jobs.length;
  7.         this.k = k;
  8.         this.jobs = jobs;
  9.         this.sum = new int[k];
  11.         int s = 0, max = 0;
  12.         for (int x : jobs) {
  13.             s += x;
  14.             max = Math.max(max, x);
  15.         }
  17.         Arrays.sort(jobs);
  18.         int l = Math.max(max, (s + k - 1) / k), r = s;
  20.         while (l < r) {
  21.             int mid = l + r >> 1;
  22.             Arrays.fill(sum, 0);
  23.             if (dfs(n - 1, mid))
  24.                 r = mid;
  25.             else
  26.                 l = mid + 1;
  27.         }
  28.         return l;
  29.     }
  31.     boolean dfs(int u, int t) {
  32.         if (u < 0)
  33.             return true;
  35.         Set<Integer> set = new HashSet<>();
  36.         for (int i = 0; i < k; i++) {
  37.             if (sum[i] + jobs[u] > t || set.contains(sum[i]))
  38.                 continue;
  39.             set.add(sum[i]);
  41.             sum[i] += jobs[u];
  42.             if (dfs(u - 1, t))
  43.                 return true;
  44.             sum[i] -= jobs[u];
  45.             if (sum[i] == 0 || sum[i] + jobs[u] == t)
  46.                 break;
  47.         }
  48.         return false;
  49.     }
  50. }

1240. 铺瓷砖

http://int-e.eu/~bf3/squares/view.html#13,11
NP困难问题，没有好的解法，爆搜

其它例题：
5289. 公平分发饼干 内含除回溯外的DP解法
Acwing 4219. 找倍数 注意取模运算的性质 10a % b = a % b * 10 % b (10a + 1) % b = (10a % b + 1 % b) % b = a((% b * 10 + 1) % b