leetcode 698. Partition to K Equal Sum Subsets 分支限界

题目

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
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.

思路

dfs 分支限界直接回溯,dfs实际上是考虑到了所有的组合的,所以不用担心排列组合导致的无法划分为k个子集的情况,代码中的 flag 标志计算使用 dfs 递归遍历所有组合

源码

class Solution {
public:
    int avg;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for(auto p:nums){
            sum+=p;
        }
        if(sum % k !=0) return false;
        avg =  sum / k;
        vector<bool> vis(nums.size(),false);
        return dfs(nums.size()-1,avg,nums,nums.size(),vis); 
    }
    bool dfs(int start,int target,vector<int> &nums,int remains,vector<bool> &vis){
        if(remains==0)return true;
        bool flag = false;
        for(int i = start;i >= 0;--i){
            if(!vis[i]&&target>=nums[i]){
                vis[i]=true;
                if(target == nums[i])flag = dfs(nums.size()-1,avg,nums,remains-1,vis);
                else flag = dfs(i-1,target-nums[i],nums,remains-1,vis);
                if(flag)return flag;
                vis[i]=false;
               // while(i>=1&&nums[i]==nums[i-1])i--;
            }
        }
        return flag;
    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注