题目描述

样例

参见原题链接

算法：搜索，参见卖女孩的小火柴一题 https://leetcode.com/problems/matchsticks-to-square/description/

关于

if (!s) {
    used[p] = false;
    return false;   
}

的说明:
因为我们枚举的思路是，拿一个数组标记一个数是否已经用到，然后枚举如何构成第一个和为sum / k的集合，如何构成第二个等.这样，当我们目前已经拼出的和s == 0，说明我们需要拼出若干个完整的sum / k的集合,且这几个集合间是无序的,而nums[p]必然要属于某个集合中，这样，当我们无法把nums[p]加入第一个集合时，自然无法加入其他任何集合.

另外这个优化，可以避免集合间无序带来的重复枚举，例如{s1, s2}, {s3, s4} + 其他集合与{s3, s4}, {s1, s2} + 其他集合是同样的解，利用这个方法可以避免重复枚举。

此外，当nums[p] + s == sum / k且搜索失败时也可以剪枝，因为长度和为nums[p]的多个数比nums[p]一个数具有更强的组合能力.

C++ 代码

class Solution {
    class SolutionImpl {
        vector<int> & nums;
        int k, n, m;
        vector<bool> used;
        bool search(int k1, int p, int s) {
            if (k1 + 1 == k) {
                return true;
            }
            for (; p < n; ++p) {
                if (used[p] || s + nums[p] > m) {
                    continue;
                }
                used[p] = true;
                if (s + nums[p] == m) {
                    if (search(k1 + 1, 0, 0)) {
                        return true;
                    } else {
                        used[p] = false;
                        return false;
                    }
                } else {
                    if (search(k1, p, s + nums[p])) {
                        return true;
                    }
                    if (!s) {
                        used[p] = false;
                        return false;
                    }
                }
                used[p] = false;

            }
            return false;
        }
    public:
        SolutionImpl(vector<int> & nums, int k) : nums(nums), k(k), n(nums.size()), used(n) {
        }
        bool calc() {
            int sum = 0;
            for (auto v : nums) {
                sum += v;
            }
            if (sum % k) {
                return false;
            }
            m = sum / k;
            return search(0, 0, 0);
        }
    };
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        return SolutionImpl(nums, k).calc();
    }
};