698. Partition to K Equal Sum Subsets

/**
 * Backtracking Solution
 *
 * Refer: 1)
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/JavaC++Straightforward-dfs-solution
 * 2)
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/JavaC++Straightforward-dfs-solution/140989
 *
 * Time Complexity: O(N * 2^N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input nums array.
 */
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length < k) {
            return false;
        }
        if (k == 1) {
            return true;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        sum /= k;
        boolean[] visited = new boolean[nums.length];

        return canPartition(nums, visited, 0, k, 0, sum);
    }

    private boolean canPartition(int[] nums, boolean[] visited, int start, int k, int curSum, int targetSum) {
        if (k == 1) {
            return true;
        }
        if (curSum > targetSum) {
            return false;
        }
        if (curSum == targetSum) {
            return canPartition(nums, visited, 0, k - 1, 0, targetSum);
        }

        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            if (canPartition(nums, visited, i + 1, k, curSum + nums[i], targetSum)) {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
}