leetcode 416 && 698. 分割等和子集   medium

leetcode 416. 分割等和子集   medium          

题目描述:

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解题思路:

因为这是要求分割成两个相等的子集,并且所有元素都是正数(其实有负数也行,只要方案数大于等于2就行),所以我们只要求有没有方案使得容量恰为数组一半和Ok了。

容量01背包,求是否存在容量恰为数组一半和的方案,所以初始化的时候注意除了dp【0】是true,其他都是false,就ojkb了

代码:

//
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //01背包,求是否存在容量恰为数组一半和的方案
        
        
        if(nums.size()<2)
            return false;
        
        int sum=0;
        for(int i:nums)
            sum += i;
        
        if(sum & 1)  // 奇数 impossible
            return false;
        sum >>= 1;
        
        vector<bool> dp(1+sum,false);
        dp[0]=true;
        for(int i:nums){
            if(dp[sum]==true) return true; // 中间可以加个速
            for(int j=sum;j>=i;--j) //01背包 容量从大到小遍历
                dp[j]=dp[j] || dp[j-i];
        }
        return dp[sum];
    }
};

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

题目描述:

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

示例 1:

输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
 

注意:

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

解题思路:

用回溯法,不能用dp来做(另外这是求集合,所以要有start开始位置这个变量,因为对于数组【1,2,3】 来说,【1,2】和【2,1】是一样的)

我们可以用递归来做,首先我们还是求出数组的所有数字之和sum,首先判断sum是否能整除k,不能整除的话直接返回false。然后需要一个visited数组来记录哪些数组已经被选中了,然后调用递归函数,我们的目标是组k个子集合,是的每个子集合之和为target = sum/k。我们还需要变量start,表示从数组的某个位置开始查找,curSum为当前子集合之和,在递归函数中,如果k=1,说明此时只需要组一个子集合,那么当前的就是了,直接返回true。如果curSum等于target了,那么我们再次调用递归,此时传入k-1,start和curSum都重置为0,因为我们当前又找到了一个和为target的子集合,要开始继续找下一个。否则的话就从start开始遍历数组,如果当前数字已经访问过了则直接跳过,否则标记为已访问。然后调用递归函数,k保持不变,因为还在累加当前的子集合,start传入i+1,curSum传入curSum+nums[i],因为要累加当前的数字,如果递归函数返回true了,则直接返回true。否则就将当前数字重置为未访问的状态继续遍历

 

我们也可以对上面的解法进行一些优化,比如先给数组按从大到小的顺序排个序,然后在递归函数中,我们可以直接判断,如果curSum大于target了,直接返回false,因为题目中限定了都是正数,并且我们也给数组排序了,后面的数字只能更大,这个剪枝操作大大的提高了运行速度

 

代码:

//
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> visited(nums.size(), false);
        return helper(nums, k, sum / k, 0, 0, visited);
    }
    bool helper(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited) {
        if (k == 1) return true;
        if (curSum == target) return helper(nums, k - 1, target, 0, 0, visited);
        for (int i = start; i < nums.size(); ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            if (helper(nums, k, target, i+1, curSum + nums[i], visited)) return true;
            visited[i] = false;
        }
        return false;
    }
};


//
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        sort(nums.begin(), nums.end(), greater<int>());
        vector<bool> visited(nums.size(), false);
        return helper(nums, k, sum / k, 0, 0, visited);
    }
    bool helper(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited) {
        if (k == 1) return true;
        if (curSum > target) return false;
        if (curSum == target) return helper(nums, k - 1, target, 0, 0, visited);  
        for (int i = start; i < nums.size(); ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            if (helper(nums, k, target, i + 1, curSum + nums[i], visited)) return true;
            visited[i] = false;
        }
        return false;
    }
};
上一篇:Action Framework Medium attribute 初始化逻辑


下一篇:CF E2 - Daleks' Invasion (medium) (LCA求两点树上路径上的最大边权)