Easy C++ Solutions With DFS


  • 0
    D

    bool helper(vector<int>& nums,vector<int> &sets, int target,int index)
    {
    if(index==(int)nums.size())
    {
    bool returnflag = true;
    for(int i=0;i<(int)sets.size();i++)
    {
    if(sets[i]!=target)
    {
    returnflag = false;
    break;
    }
    }
    return returnflag;
    }
    for(int i=0;i<sets.size();i++)
    {
    if(sets[i]+nums[index]>target) continue;
    sets[i]+=nums[index];
    if(helper(nums,sets,target,index+1)) return true;
    sets[i]-=nums[index];
    }
    return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k)
    {
    vector<int> sets(k,0);
    int sum = accumulate(nums.begin(),nums.end(),0);
    if(sum%k!=0) return false;
    int target = sum/k;
    bool ans = helper(nums,sets,target,0);
    return ans;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.