$Pre$

在一些枚举方案的问题中，会存在”后效性”的问题，这种时候就不能用局部最优来形成全局最优解

一、$Leetcode.698$划分为$K$个相等的子集

本题分析完毕后就是要凑齐$K$个值为$val$的集合，那么直观的思路是判断是否可以凑出$K$次$val$，同时每次将选了的数标记已访问，代码如下：

class Solution {
public:
    bool dfs(int u, int sum, vector<int> &nums, int n)
    {
        if (!sum) return true;
        if (u == n) return false;
        // 不选当前数
        if (dfs(u + 1, sum, nums, n)) return true;  
        // 只有当当前结点没有被选的时候才可以选当前数
        if (!st[u])
        {
            st[u] = true;
            if (dfs(u + 1, sum - nums[u], nums, n)) return true;
            st[u] = false;
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0, n = nums.size();
        sort(nums.begin(), nums.end());
        for (auto t : nums) sum += t;
        if (sum % k) return false;
        if (nums[n - 1] > sum / k) return false;

        int val = sum / k;
        for (int i = 0; i < k; i ++)  // 凑k个val
            if (!dfs(0, val, nums, n)) return false;
        return true;
    }
private:
    static const int N = 20;
    bool st[N];
};

可以发现这种选法的每一次选数，其实都是具有后效性的，因为$k$此选数之间是相互影响的，比如我们已有$4,3,3,2,2,1$，要凑出$3$个$5$，那么明显是可以的，但是如果我们先将$2,2,1$选了，那么在这种策略下我们后面两次就无法进行，但是实际上是可以凑出$3$个$5$的
因此我们应该同时进行$K$次的选数，保证各次之间互不影响

class Solution {
public:
    // last每次凑val时nums上次遍历到的位置
    bool dfs(int last, int sum, int k, vector<int> &nums, int n)
    {
        if (k == 0) return true;
        if (sum < 0) return false;
        if (sum == val) return dfs(0, 0, k - 1, nums, n);
        for (int i = last; i < n; i ++)
            if (!st[i] && val - sum >= nums[i])
            {
                st[i] = true;
                if (dfs(i + 1, sum + nums[i], k, nums, n)) return true;
                st[i] = false;
                if (sum == 0) return false;
            }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0, n = nums.size();
        sort(nums.begin(), nums.end(), greater<int>());
        for (auto t : nums) sum += t;
        if (sum % k) return false;
        if (nums[n - 1] > sum / k) return false;
        val = sum / k;
        if (dfs(0, 0, k, nums, n)) return true;
        return false;
    }
private:
    int val;
    static const int N = 20;
    bool st[N];
};

二、$Acwing.1027$方格取数