public class Solution {
    public bool CanPartitionKSubsets(int[] nums, int k) {
        int[] setSum = new int[k];
        Dictionary<string, bool> dp = new Dictionary<string, bool>();
        int sum = 0;
        for (int i=0; i<nums.Length; i++)
        {
            sum += nums[i];
        }
        
        if (k == 1)
        {
            return true;
        }
        
        if (sum%k != 0)
        {
            return false;
        }
        
        return Helper(nums, 0, setSum, sum/k, visited, dp);
    }
    
    private bool Helper(int[] nums, int i, int[] setSum, int targetSum, Dictionary<string, bool> dp)
    {
        string key = i + "," + string.Join(",", setSum);
        
        if (dp.TryGetValue(key, out bool res))
        {
            return res;
        }
        
        if (i == nums.Length)
        {
            for (int j=1; j<setSum.Length; j++)
            {
                if (setSum[j] != setSum[j-1])
                {
                    dp.Add(key, false);
                    return false;
                }
            }
            dp.Add(key, true);
            return true;
        }
        
        bool result = false;
        for (int j=0; j<setSum.Length; j++)
        {
            if (setSum[j]+nums[i] <= targetSum)
            {
                setSum[j] += nums[i];
                result |= Helper(nums, i+1, setSum, targetSum, dp);
                setSum[j] -= nums[i];
                
                if (result == true)
                {
                    dp.Add(key, result);
                    return true;
                }
            }
        }
        
        dp.Add(key, result);
        return result;
    }
}