首页 > 其他 > 详细

划分为k个相等的子集(dfs)

时间:2019-09-10 20:42:36      阅读:89      评论:0      收藏:0      [点我收藏+]

题目连接:

https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets/

题目大意:

中文题目

具体思路:

dfs 暴力搜索,注意一个优化的地方。在凑的过程中,记录一个下标,下一次就从这个下标开始的地方往后找;当凑齐一对的时候就重新从 0 开始 搜索

AC代码:

 1 class Solution {
 2 public:
 3 
 4     bool canPartitionKSubsets(vector<int>& nums, int k) {
 5     
 6         int vis[20];
 7         int sum = 0 ;
 8         
 9         memset(vis , 0 , sizeof(vis));
10         for(auto i : nums){
11             sum += i;
12         }
13         if(sum % k != 0)
14             return false;
15         else{ 
16             return dfs(vis , k , sum / k, 0 , 0 ,nums);
17         }
18     }
19     
20    bool dfs(int vis[] , int k , int sum , int tmp_sum , int id ,vector<int> & nums){
21         
22        if(k == 0) return true;
23        
24       //  if(k < 0 || tmp_sum > sum )false;
25         
26         if( tmp_sum == sum )
27            return  dfs(vis , k - 1, sum , 0 , 0 ,nums);
28         
29         else{
30         int len = nums.size();
31         
32         for(int i = id ; i < len ; i++ ){
33             if(vis[i]) continue;
34             vis[i] = 1;
35             if(tmp_sum + nums[i] <= sum)
36             if(dfs(vis , k , sum , tmp_sum + nums[i] , id + 1, nums))
37                 return true;
38             vis[i] = 0;
39         }
40         }
41         return false;
42     }
43 };

 

划分为k个相等的子集(dfs)

原文:https://www.cnblogs.com/letlifestop/p/11502570.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!