using System;

using System.Collections.Generic;                   

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

    public static bool CanPartitionKSubsets(int[] nums, int k) {

        //Implementation with Backtracking

        int totalSum = 0;

        for(int i=0; i < nums.Length; i++)

        {

            totalSum += nums[i];

        }

        if(totalSum % k != 0)

            return false;

        int targetSum = totalSum / k;

        if(totalSum % k != 0)

            return false;

        used = new bool[nums.Length];

        Array.Sort(nums, new Comparison<int>((i1, i2) => i2.CompareTo(i1)));

        return backtrack(0, k, 0, nums, targetSum);

    }

    private static bool[] used;

    private static bool backtrack(int i, int k, int subsetSum, int[] nums, int target)

    {

        if(k == 0)

            return true;

        if(subsetSum == target)

        {

            return backtrack(0, k-1, 0, nums, target);

        }

        for(int j =i; j < nums.Length; j++)

        {

            if(used[j] || subsetSum + nums[j] > target)

                continue;

            used[j] = true;

            if(backtrack(j+1, k, subsetSum+nums[j], nums, target))

                return true;

            used[j] = false;                

        }

        return false;

    }

}