698. Partition to K Equal Sum Subsets

backtracking time O(2ⁿ) space O(n)
每次递归的深度是O(n)
先找到target，然后对数组从大到小排序，用回溯试数即可

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false; // 这行必须要有！全靠后边handle速度太慢！
        int n = nums.size();
        vector<bool> v(n);
        return dfs(target, nums, v, k, target); // 从target往下减
    }

    bool dfs(int s, const vector<int> &A, vector<bool> &v, int k, int target) {
        if (k == 0) return true; // 找到了k组
        // if (s < 0) return false; // 不合要求
        if (s == 0) return dfs(target, A, v, k - 1, target); // 找到一组可能的，尝试找下一组
        for (int i = 0; i < A.size(); ++i) {
            if (v[i] || A[i] > s) continue;
            // if (A[i] > s) return false; // 这行能加速？！匪夷所思
            v[i] = true;
            if (dfs(s - A[i], A, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

最快版本

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false;
        int n = nums.size();
        vector<bool> v(n);
        return dfs(target, nums, 0, v, k, target);
    }

    bool dfs(int s, const vector<int> &A, int b, vector<bool> &v, int k, int target) {
        if (k == 0) return true;
        if (s < 0) return false;
        if (s == 0) return dfs(target, A, 0, v, k - 1, target); // 注意是从0开始，因为找到一组并不意味着前边的都放到某个组里了，只能从头再找
        for (int i = b; i < A.size(); ++i) {
            if (v[i]) continue;
            v[i] = true;
            if (dfs(s - A[i], A, i + 1, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end(), greater<int>());
        if (nums[0] > target) return false;
        int n = nums.size();
        vector<bool> v(n);
        // int i = 0; // 跳过那些自成一组的
        // for (; i < n && nums[i] == target; ++i) {
        //     v[i] = true;
        //     --k;
        // }
        return dfs(0, nums, v, k, target);
    }

    bool dfs(int s, const vector<int> &A, vector<bool> &v, int k, int target) {
        if (s > target) return false;
        if (s == target) {
            s = 0;
            if (--k == 0) return true;
        }
        for (int i = 0; i < A.size(); ++i) {
            if (v[i] || s + A[i] > target) continue;
            v[i] = true;
            if (dfs(s + A[i], A, v, k, target)) return true;
            v[i] = false;
        }
        return false;
    }
};

状态压缩dp O(n*2ⁿ) time O(2ⁿ) space
f[state]表示该state所指的这些数可以凑成多个和为target的partition外加一个和小于等于target的一部分，target是sum/k
s[state]为对应state所指的这些数构成的和
f[0] = true
对于每个state从小到大尝试加数看能不能凑成新的和为target的partition，即使不能凑成，能缩小gap也行，因为已知总和一定能被k和target整除

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        int target = sum / k;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (nums[n - 1] > target) return false;
        vector<int> s(1 << n);
        vector<bool> f(1 << n);
        f[0] = true;
        for (int state = 0; state < (1 << n); ++state) {
            if (!f[state]) continue;
            for (int i = 0; i < n; ++i) {
                int next = state | (1 << i);
                if (next != state && !f[next]) {
                    if (nums[i] <= target - s[state] % target) {
                        f[next] = true;
                        s[next] = s[state] + nums[i];
                    } else break;
                }
            }
        }
        return f[(1 << n) - 1];
    }
};