698. Partition to K Equal Sum Subsets

Version #1 DFS

89.41 % 

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || k <= 0 || nums.length < k) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums); // Must sort and add from larger elements
        boolean[] visited = new boolean[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!visited[i] && !partition(nums, i, visited, target)) return false;
        }
        return true;
    }
    public boolean partition(int[] nums, int start, boolean[] visited, int target) {
        if (nums[start] > target) return false;
        // nums[start] <= target
        visited[start] = true;
        if (nums[start] == target) {
            return true; // no need to reset, marked as visited
        }
        for (int i = start - 1; i >= 0; i--) {
            if (visited[i]) continue; // make sure nums[i] is not visited
            if (partition(nums, i, visited, target - nums[start])) return true;
        }
        visited[start] = false;
        return false;
    }
}