划分为k个相等的子集 动态规划求解

1. 状态定义：用一个二维数组dp[i][j]表示当前是否能用前i个数划分出j个和为sum/k的子集。

2. 状态转移方程：假设当前已经处理了前i-1个数，现在要考虑第i个数：

- 如果第i个数可以添加到已有的某个子集中，那么dp[i][j] = dp[i-1][j] || dp[i-1][j-1]；
- 如果第i个数不能添加到已有的某个子集中，则dp[i][j] = dp[i-1][j]。

其中，dp[i-1][j]表示当前第i个数不参与划分，dp[i-1][j-1]表示当前第i个数参与划分。

3. 边界条件：dp[0][0] = true，表示不处理任何数时可以划分出和为0的子集；其他初始化为false。

4. 最终答案：如果dp[n][k]为true，则可以用前n个数划分出k个和为sum/k的子集。

完整代码如下：

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int n = nums.size();
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    int target = sum / k;
    vector<vector<bool>> dp(n+1, vector<bool>(k+1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = true;
        for (int j = 1; j <= k; j++) {
            if (nums[i-1] > target) continue;
            if (dp[i-1][j] || dp[i-1][j-1] && nums[i-1] <= target) {
                dp[i][j] = true;
            }
        }
    }
    return dp[n][k];
}