【Lintcode】1220. Matchsticks to Square

题目地址：

https://www.lintcode.com/problem/matchsticks-to-square/description

给定一个数组$A$，问是否可以将$A$的所有数分成四个不相交子集，使得每个子集的和相等。题目保证数组只包含正整数。

思路是DFS（这个问题是一个NPC问题，暂时没有多项式解法，只能暴力搜索）。首先排除一些不可能的情形。如果总和$s$不能被$4$整除，那肯定不可能；如果数组最大值大于$s/4$，那也肯定不可能。接下来就直接暴力搜索所有情况了，每次先搜出一个和为$s/4$的子集，然后再在剩余没选过的数里继续搜出和为$s/4$的子集，如果一旦能恰好找到$4$个和为$s/4$的子集，并且每个数都被用过了，说明找到答案了，返回true；如果枚举了所有情况也没发现答案，则返回false。对于搜索而言，可以先从大到小对$A$排序，先对大的数搜索，可以更好的剪枝。代码如下：

public class Solution {
    /*** @param nums: an array* @return: whether you could make one square using all the matchsticks the little match girl has*/public boolean makesquare(int[] nums) {
    // Write your code hereif (nums == null || nums.length == 0) {
    return false;}int sum = 0;for (int i = 0; i < nums.length; i++) {
    sum += nums[i];}// 和不是4的倍数，返回falseif (sum % 4 != 0) {
    return false;}// 对nums从大到小排序，Arrays.sort(nums);reverse(nums);// 有数大于总和的四分之一，也返回falsesum /= 4;if (nums[0] > sum) {
    return false;}return dfs(nums, new boolean[nums.length], 0, sum, 0);}// used记录已经用过的数，curSum记录当前得到的和，sum记录需要达到的和，count记录已经找到了多少个和为sum的子集了private boolean dfs(int[] nums, boolean[] used, int curSum, int sum, int count) {
    // 如果已经找到了4个和为sum的子集，那就看一下是不是所有数都被用到了，如果是，则找到了，返回true，否则返回falseif (count == 4) {
    for (int i = 0; i < used.length; i++) {
    if (!used[i]) {
    return false;}}return true;}// 如果得到了一个和为sum的子集，那就尝试重新搜索出下一个和为sum的子集，并计count加1；如果能找到，则返回true；// 注意，这里即使找不到，也不要返回false，因为有可能需要把当前找到的和为sum的子集拆开重新枚举if (curSum == sum && dfs(nums, used, 0, sum, count + 1)) {
    return true;}// 开始枚举哪个数加入当前枚举的子集中for (int i = 0; i < nums.length; i++) {
    if (used[i]) {
    continue;}// 每次枚举子集的时候，同一个数只枚举连续的一段，减少重复枚举if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;}if (curSum + nums[i] <= sum) {
    used[i] = true;if (dfs(nums, used, curSum + nums[i], sum, count)) {
    return true;}// 回溯的时候恢复现场used[i] = false;}}return false;}private void reverse(int[] nums) {
    for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
    int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}
}

时间复杂度是指数级的，空间$O(n)$。