Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

&nbsp;
Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.


Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false


&nbsp;
Constraints:


	1 &lt;= k &lt;= nums.length &lt;= 16
	1 &lt;= nums[i] &lt;= 104
	The frequency of each element is in the range [1, 4].


class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(idx,curr,cnt,limit):
            if cnt == k:
                return True
            if curr ==limit:
                return dfs(0,0,cnt+1,limit)

            i = idx
            while i < len(nums):
                if visited[i] or nums[i]+curr > limit:
                    i += 1
                    continue
                visited[i] = True
                if dfs(i+1,curr+nums[i],cnt,limit):
                    return True
                visited[i] = False

                while i+1 < len(nums) and nums[i] == nums[i+1]: #pruning1
                    i += 1
                if curr == 0 or curr + nums[i] == limit: #pruning2
                    return False
                i += 1
            return False

        if len(nums) < k or sum(nums) % k:
            return False
        numSum = sum(nums)

        for i in range(len(nums)):
            if nums[i] > numSum//k:
                return False

        visited = [False]*len(nums)
        return dfs(0,0,0,numSum//k)
class Solution {
    private final List<Set<Integer>> allSubsets = new ArrayList<>();
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if(sum % k != 0) return false;
        getAllSubsets(nums.length, sum / k, new HashSet<>(), nums, false);
        return allSubsets.size() >= k && canPartition(allSubsets.size(), k, nums.length, new HashSet<>());
    }

    private boolean canPartition(int n, int k, int size, Set<Integer> current) {
        if(k == 0 && current.size() == size) return true;
        if(n == 0 || k < 0) return false;
        boolean addSet = false;
        if(allUnique(current, allSubsets.get(n-1))) {
            current.addAll(allSubsets.get(n - 1));
            addSet = canPartition(n - 1, k - 1, size, current);
            current.removeAll(allSubsets.get(n - 1));
        }
        return addSet || canPartition(n - 1, k, size, current);
    }

    private void getAllSubsets(int n, int targetSum, Set<Integer> subsets, int[] nums, boolean lol) {
        if(targetSum == 0) {
            allSubsets.add(new HashSet<>(subsets));
            return;
        }
        if (n == 0 || targetSum < 0) return;
        subsets.add(n-1);
        getAllSubsets(n-1, targetSum - nums[n-1], subsets, nums, true);
        subsets.remove(n-1);
        getAllSubsets(n-1, targetSum, subsets, nums, false);
    }
    
    private boolean allUnique(Set<Integer> set1, Set<Integer> set2) {
        for (Integer num: set1) if(set2.contains(num)) return false;
        return true;
    }
}
class Solution {
public:
    unordered_map<string, int> dp;
    int solve(vector<int>& nums, int target, int remain, int i, int vis, int k){
        if( k == 1) return 1;

        //memorization addition
        string t = to_string(i)+"_"+to_string(remain)+"_"+to_string(k)+"_"+to_string(vis);
        if(dp.find(t) != dp.end()) return dp[t];

        if(remain == 0){
            return dp[t] = solve(nums, target, target, nums.size()-1, vis, k - 1);
        }
        for(int j = i; j >= 0; --j){
            if(((vis>>j)& 1) || remain - nums[j] < 0) continue;
            vis = vis | (1 << j );
            if(solve(nums, target, remain - nums[j], j - 1, vis, k) ) return dp[t] = 1;
            vis = vis & ~(1<<j);
        }
        return dp[t] = 0;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum%k != 0) return false;
        int vis = 0;
        return solve(nums, sum/k, sum/k, nums.size()-1, vis, k);
    }
};
var canPartitionKSubsets = function(nums, k) {
    const sum = nums.reduce((sum, num) => sum + num);
    const divide = sum / k;
    if (!Number.isInteger(divide)) return false;
    const subsets = Array(k).fill(0);
    const dfs = (index = 0) => {
        if (index >= nums.length) return true;
        const visited = new Set();
        const num = nums[index];

        for (let sub = 0; sub < k; sub++) {
            const subset = subsets[sub];
            if (visited.has(subset) || subset + num > divide) continue;

            visited.add(subset);
            subsets[sub] += num;
            if (dfs(index + 1)) return true;
            subsets[sub] -= num;
        }
        return false;
    };

    nums.sort((a, b) => b - a);
    return dfs();
};
Partition to K Equal Sum Subsets