Partition to K Equal Sum Subsets

LeetCode Q 698 - Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

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

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

Solution : Backtracking

Code:

public boolean canPartitionKSubsets(int[] nums, int k) {
	if (nums.length < k || k == 0) return false;
	if (k == 1) return true;

	int sum = 0;
	for(int num: nums) sum += num;
	if (sum % k != 0) return false;
	sum /= k;

	return backtrack(nums, k, sum, 0, 0, new boolean[nums.length]);
}

private boolean backtrack(int[] nums, int k, int targetSum, int currSum, int index, boolean[] visited) {
	
	// boundary cases
	if (k == 1) return true;
	else if (currSum == targetSum) 
		return backtrack(nums, k - 1, targetSum, 0, 0, visited);
	else if (currSum > targetSum)
		return false;

	// keep recursion:
	for (int i = index; i < nums.length; i++) {
		if (!visited[i]) {
			visited[i] = true; //choose
			if (dfs(nums, k, targetSum, currSum + nums[i], i + 1, visited))   // explore
				return true;
			visited[i] = false; // unchoose
		}
	}

	return false;
}