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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], k = 3
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 16</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
	<li>The frequency of each element is in the range <code>[1, 4]</code>.</li>
</ul>

class Solution {
public:
    bool find(int i, int currSum, int mask, int k, int n, int target,
              vector<int>& nums, vector<int>& dp) {
        if (k == 1)
            return true;

        if (currSum == target)
            return find(0, 0, mask, k - 1, n, target, nums, dp);
        if (i == n)
            return false;

        if (dp[mask] != -1)
            return dp[mask];

        bool pick = false, notPick = false;

        if (!(mask & (1 << i)) && currSum + nums[i] <= target) {
            mask = mask | (1 << i); // Set the ith bit of the mask to mark the
                                    // element as used
            pick = find(i + 1, currSum + nums[i], mask, k, n, target, nums, dp);
            mask =
                mask ^
                (1
                 << i); // Clear the ith bit to backtrack and try other elements
        }
        notPick = find(i + 1, currSum, mask, k, n, target, nums, dp);

        return dp[mask] = pick || notPick;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(begin(nums), end(nums), 0);
        if (sum % k == 1)
            return false;
        int target = sum / k;

        int n = nums.size();
        vector<int> dp((1 << n), -1);
        int mask = 0;
        return find(0, 0, mask, k, n, target, nums, dp);
    }
};

/*class Solution {
public:
    int n;
    int subsetValue;


    bool helper(vector<int>& nums, int k, int mask, int currentSum, vector<int>&
dp) {
        // Base case: All subsets have been formed
        if (k == 0) {
            // Check if all elements of the input array have been used (mask is
full) return mask == (1 << n) - 1;
        }

        // If the current subset has reached the target value, move on to the
next subset if (currentSum == subsetValue) { return helper(nums, k - 1, mask, 0,
dp);
        }

        // Check if the current state has been memoized
        if (dp[mask] != -1) {
            return dp[mask];
        }

        bool ans = false;
        for (int i = 0; i < n; i++) {
            // Skip elements that have already been used in the current subset
            if (mask & (1 << i)) {
                continue;
            }

            // Try adding the current element to the current subset if it
doesn't exceed the target value if (currentSum + nums[i] <= subsetValue) { int
newMask = mask | (1 << i);   // Set the ith bit of the mask to mark the element
as used ans = ans || helper(nums, k, newMask, currentSum + nums[i], dp); newMask
^= (1 << i);             // Clear the ith bit to backtrack and try other
elements
            }
        }

        // Memoize the result for the current state
        return dp[mask] = ans;
    }

    // Main function to check if the array can be partitioned into k subsets
with equal sum bool canPartitionKSubsets(vector<int>& nums, int k) { n =
nums.size(); int sum = accumulate(nums.begin(), nums.end(), 0); subsetValue =
sum / k;

        // If the total sum is not divisible by k, partition is not possible
        if (sum % k != 0) {
            return false;
        }

        vector<int> dp((1 << n) - 1, -1);   // Memoization array to store
results for subsets return helper(nums, k, 0, 0, dp);
    }
};*/
/* Certainly! Bitmasking is a clever technique used in this code to efficiently
keep track of which elements of the array have been used in subsets. Let's break
down how bitmasking is applied and why it is useful in this context.

### Problem Recap
The problem is to determine if the array `nums` can be partitioned into `k`
subsets where each subset has the same sum. The key challenge is to explore
different combinations of elements and to efficiently remember which
combinations have already been considered.

### Bitmasking Concept
A bitmask is essentially a sequence of bits (0s and 1s) where each bit
represents the state (used or not used) of a corresponding element in the array.

- If the `i`-th bit of a bitmask is `1`, it means the `i`-th element of the
array has been included in the current subset.
- If the `i`-th bit of a bitmask is `0`, it means the `i`-th element has not
been included yet.

### Bitmask Representation in the Code
- `mask` is an integer that serves as a bitmask where the binary representation
indicates which elements of `nums` have been included in the current
configuration of subsets.
- If `n` is the size of the array `nums`, then `mask` will be an integer ranging
from `0` to `(1 << n) - 1`. This range covers all possible combinations of
elements (from none being used to all being used).

### How Bitmasking is Used
1. **Tracking Element Usage**: The bitmask `mask` helps keep track of which
elements are currently included in the subsets being formed.
   - For example, if `mask = 5` and `n = 3`, the binary representation of `mask`
is `101`, which means the 0th and 2nd elements of the array have been included,
while the 1st element has not.

2. **Checking and Setting Bits**:
   - The condition `if (mask & (1 << i))` checks if the `i`-th element is
already included in the current subset.
   - The operation `mask | (1 << i)` sets the `i`-th bit to `1`, indicating that
the `i`-th element has now been used.

3. **Memoization Using Bitmask**:
   - The array `dp` is used to store the results of previously computed states,
indexed by the bitmask. If `dp[mask]` has already been computed (i.e., not
`-1`), it means that the function has already checked the current combination of
elements and whether they can form the required subsets.
   - This avoids redundant computation, making the algorithm more efficient.

4. **Recursion with Backtracking**:
   - The function `helper` tries to form subsets by recursively including each
unused element in the current subset. If the current subset reaches the desired
sum (`subsetValue`), the function moves on to form the next subset.
   - The bitmask ensures that each element is only used once per subset
configuration, and the recursion explores all valid combinations of subsets.

5. **Base Case and Full Mask**:
   - The base case `if (k == 0)` checks if all subsets have been successfully
formed. The condition `mask == (1 << n) - 1` ensures that all elements have been
used.

### Summary
Bitmasking allows the algorithm to compactly represent and efficiently check the
usage state of all elements in the array, enabling the algorithm to explore all
possible subset configurations while avoiding redundant calculations. This is
especially powerful in problems where you need to track the inclusion/exclusion
of elements across multiple recursive calls.*/
26574