leetcode 698. Partition to K Equal Sum Subsets K个相等子集 + 深度优先搜索DFS

男娘i 2022-06-03 08:50 113阅读 0赞

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:  
Input: nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
Output: True  
Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.  
Note:

1 <= k <= len(nums) <= 16.  
0 < nums\[i\] < 10000.

本题题意很简单，直接深度优先搜索即可

如果k=1，说明此时只需要组一个子集合，那么当前的就是了，直接返回true。如果curSum等于target了，那么我们再次调用递归，此时传入k-1，start和curSum都重置为0，因为我们当前又找到了一个和为target的子集合，要开始继续找下一个。否则的话就从start开始遍历数组，如果当前数字已经访问过了则直接跳过，否则标记为已访问。然后调用递归函数，k保持不变，因为还在累加当前的子集合，start传入i+1，curSum传入curSum+nums\[i\]，因为要累加当前的数字，如果递归函数返回true了，则直接返回true。否则就将当前数字重置为未访问的状态继续遍历

**需要注意的是需要添加start做位index的起始点，否者会超时**

建议和[leetcode 416. Partition Equal Subset Sum 动态规划DP + DFS深度优先遍历][leetcode 416. Partition Equal Subset Sum _DP _ DFS] 一起学习

**这道题其实还是蛮难的，需要考虑到index、currsum、k三个情况的处理，所以这道题很值得学习，对了还有一个visit标记数组**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        bool canPartitionKSubsets(vector<int>& nums, int k)
        {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum%k != 0)
                return false;
            vector<bool> visit(nums.size(), false);
            return dfs(nums, k, sum / k, 0, 0, visit);
        }
    
        bool dfs(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited)
        {
            if (k == 1)
                return true;
            else if (curSum > target)
                return false;
            else if (curSum == target)
                return dfs(nums, k - 1, target, 0, 0, visited);
            else
            {
                for (int i = start; i < nums.size(); ++i)
                {
                    if (visited[i] == false)
                    {
                        visited[i] = true;
                        if (dfs(nums, k, target, i + 1, curSum + nums[i], visited))
                            return true;
                        visited[i] = false;
                    }
                }
                return false;
            }
        }
    };

[leetcode 416. Partition Equal Subset Sum _DP _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78752598