1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution
{
public:
    int target = 0;               // 每个子集的目标和
    std::vector<bool> st;        // 标记数组：记录元素是否被使用

    // 回溯搜索函数
    bool dfs(std::vector<int>& nums, int u, int cur, int k)
    {
        if (k == 0) return true;                        // 成功划分成 k 个子集
        if (cur == target)                              // 当前子集满了，开始下一个
            return dfs(nums, 0, 0, k - 1);

        for (int i = u; i < nums.size(); ++ i)
        {
            if (!st[i])
            {
                if (cur + nums[i] <= target)            // 不超过目标和
                {
                    st[i] = true;
                    if (dfs(nums, i + 1, cur + nums[i], k))
                        return true;
                    st[i] = false;                      // 回溯
                }

                // 跳过重复数字，避免冗余递归
                while (i + 1 < nums.size() && nums[i] == nums[i + 1])
                    ++ i;
            }
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k)
    {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % k) return false;                      // 不能整除，无法划分

        target = sum / k;
        st = std::vector<bool>(nums.size());

        sort(nums.begin(), nums.end());                 // 优化搜索顺序（方便剪枝）
        return dfs(nums, 0, 0, k);
    }
};