Leetcode 698. 划分为k个相等的子集 解题思路及C++实现

解题思路：

这是一个典型的深度优先搜索问题。使用一个相同大小的数组visited来记录元素是否被访问过（即是被已被划分到相应的子集中）。

每找到一个划分子集，相应对k减一，再继续执行深度优先搜索程序。

 

class Solution { public:bool canPartitionKSubsets(vector<int>& nums, int k) {int sum = accumulate(nums.begin(), nums.end(), 0); //求总和if(sum % k != 0) return false; //如果总和不能被平均分配到k份，就返回falsevector<bool> visited(nums.size(), false); //记录元素是否已经被划分过return dfs(nums, visited, 0, sum/k, 0, k);}bool dfs(vector<int>& nums, vector<bool>& visited, int start, int target, int cursum, int k){if(k == 1) return true; //只剩下一个待分集合，就可以直接返回true了else if(cursum > target) return false;else if(cursum == target) return dfs(nums, visited, 0, target, 0, k-1); //找到一个分配集合，则要将搜索起始位置start重置为0，待分配子集剩下k-1个else{for(int i = start; i < nums.size(); i++){ //从start开始找if(visited[i] == false){ //看是否已被访问过visited[i] = true; //访问当前元素if(dfs(nums, visited, i+1, target, cursum+nums[i], k)) return true;visited[i] = false;}}return false;}} };

 

 

 

总结

以上是生活随笔为你收集整理的Leetcode 698. 划分为k个相等的子集 解题思路及C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。