Luobuyu's Blog

0%

698. 划分为k个相等的子集

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 4.6k 阅读时长 ≈ 4 分钟
可以从两种视角解决，排列问题的两种视角。

698.划分为k个相等的子集

题目描述：

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

数据范围：

$1\le k \le nums.len \le 16; 0\lt nums[i] \lt 10^4;$

每个元素的频率都在 $[1,4]$ 之间。

题解：

从输入数字的视角：

需要为每个数字选择一个桶放入，为每个数字遍历 $k$ 个桶，找到一个合适的桶放入。可以写出类似下面这个代码

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
47
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    bool canPartitionKSubsets(vector<int> &nums, int k)
    {
        int sum = 0;
        int maxx = 0;
        for (auto &x : nums)
        {
            sum += x;
            maxx = max(maxx, x);
        }
        int target = sum / k;
        if (sum % k || maxx > target)
            return false;
        int n = nums.size();
        sort(nums.begin(), nums.end(), [](const int &x, const int &y)
             { return x > y; }); // 小剪枝
        vector<int> bucket(k);
        function<bool(int)> dfs = [&](int step)
        {
            if (step == n)
            {
                for (int i = 0; i < k; ++i)
                {
                    if (bucket[i] != target)
                        return false;
                }
                return true;
            }
            for (int i = 0; i < k; ++i)
            {
                if (bucket[i] + nums[step] > target)
                    continue;
                bucket[i] += nums[step];
                if (dfs(step + 1))
                    return true;
                bucket[i] -= nums[step];
            }
            return false;
        };
        return dfs(0);
    }
};

排序，将大的放前面，可以降低搜索树的高度，从而剪枝。但是复杂度还是很高，过不了。复杂度是 $O(k^n)$ ，指数级。考虑剪枝

  • 首先排序剪枝，大的放前面。
  • 然后每次创建新分支时，先判断能不能放入，不能放入直接 continue。这样的话其实 $step == n$ 一定是合法解，因为这时所有的球都放完了。
  • 重复元素优化，因为当两个桶的容量相同时，该数字放哪个桶效果都是一样的，类似重复数字剪枝。牛，直接 $0ms$ 通过。

image-20230928160425798

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
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    bool canPartitionKSubsets(vector<int> &nums, int k)
    {
        int sum = 0;
        int maxx = 0;
        for (auto &x : nums)
        {
            sum += x;
            maxx = max(maxx, x);
        }
        int target = sum / k;
        if (sum % k || maxx > target)
            return false;
        int n = nums.size();
        sort(nums.begin(), nums.end(), [](const int &x, const int &y)
             { return x > y; }); // 小剪枝
        vector<int> bucket(k);
        function<bool(int)> dfs = [&](int step)
        {
            if (step == n) return true;
            for (int i = 0; i < k; ++i)
            {
                if (bucket[i] + nums[step] > target || i > 0 && bucket[i] == bucket[i-1])
                    continue;
                bucket[i] += nums[step];
                if (dfs(step + 1))
                    return true;
                bucket[i] -= nums[step];
            }
            return false;
        };
        return dfs(0);
    }
};

从桶的视角：

为每个桶遍历所有的球，选择没有被选过的球，并且不会溢出的球放入。装满一个桶之后递归遍历下一个桶。

结束条件：

1
if(k == 0)

可以写出如下代码：

需要注意如果在分支得到了 $true$ ，直接返回 $true$ 就行了。

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    bool canPartitionKSubsets(vector<int> &nums, int k)
    {
        int sum = 0;
        int maxx = 0;
        for (auto &x : nums)
        {
            sum += x;
            maxx = max(maxx, x);
        }
        int target = sum / k;
        if (sum % k || maxx > target)
            return false;
        int n = nums.size();
        sort(nums.begin(), nums.end(), [](const int &x, const int &y)
             { return x > y; }); // 小剪枝
        vector<bool> vis(n, false);
        // step 表示当前桶
        function<bool(int, int, int)> dfs = [&](int step, int index,int curSum)
        {
            if (step == 0)
                return true;
            if (curSum == target)
                return dfs(step - 1, 0, 0);
            for (int i = index; i < n; ++i)
            {
                if (vis[i] || curSum + nums[i] > target)
                    continue;
                vis[i] = true;
                if (dfs(step, i + 1, curSum + nums[i]))
                    return true;
                vis[i] = false;
            }
            return false;
        };
        return dfs(k, 0, 0);
    }
};

但是还是会超时，复杂度为 $O((2^n)^k)$ 。其实上面的代码在递归的过程中存在很多冗余的计算，导致超时。

比如 1,2,4,3,...... ，target = 5，第一个桶会先选择 1,4。第二个桶会选择 2,3。假设后面的无法组合完成，则程序会进行回溯。假设回溯到了 $1$ 号桶的第 $1$ 次选择，那么 $1$ 号桶会选择 $2$ ，就变成了 $1$ 号桶 2,3， $2$ 号桶 1,4。 剩下的仍然无法组合出正确答案。因此需要考虑剪枝。可以使用记忆化操作，使用一个整数使用位运算记录状态。

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
47
48
49
50
51
52
53
54
55
56
57
58
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    bool canPartitionKSubsets(vector<int> &nums, int k)
    {
        int sum = 0;
        int maxx = 0;
        for (auto &x : nums)
        {
            sum += x;
            maxx = max(maxx, x);
        }
        int target = sum / k;
        if (sum % k || maxx > target)
            return false;
        int n = nums.size();
        sort(nums.begin(), nums.end(), [](const int &x, const int &y)
             { return x > y; }); // 小剪枝
        unordered_map<int, bool> dp;
        int state = 0;
        // step 表示当前桶
        function<bool(int, int, int)> dfs = [&](int step, int index, int curSum)
        {
            if (step == 0)
                return true;
            if (curSum == target)
            {
                dp[state] = dfs(step - 1, 0, 0);
                return dp[state];
            }
            if (dp.count(state))
                return dp[state];
            for (int i = index; i < n; ++i)
            {
                if (((state >> i) & 1) || curSum + nums[i] > target)
                    continue;
                state |= 1 << i;
                if (dfs(step, i + 1, curSum + nums[i]))
                    return true;
                state ^= 1 << i;
                while (i + 1 < n && nums[i + 1] == nums[i])	// 这个地方加速了非常多。
                    ++i;
            }
            return false;
        };
        return dfs(k, 0, 0);
    }
};