class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {

        int n = nums.size();
        int sm = 0;
        for(auto s:nums)sm+=s;

        if(sm%k!=0||k==0)return false;
        vector<int>visit(n+1, 0);
        sm = sm/k;

        return f(nums, visit,  0, sm, k, 0);

    }

    bool f(vector<int>& nums, vector<int>& visit, int cur,int sm, int k,int st)
    {
        if(k == 1)
        {
            return true;
        }

        if(sm == cur){
         return f(nums, visit, 0, sm , k-1, 0);
        }

        for(int i=st;i<nums.size();i++)
        {
            if(!visit[i])
            {
                visit[i] = 1;

               if(f(nums, visit, cur+nums[i], sm, k, i+1))return true;
                visit[i] = 0;
            }


        }

        return false;
    }
};