698 Partition to K Equal Sum Subsets

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k > 0) return false;
        int target = sum / k;

        int row = nums.length - 1;
        if (row > 0 && nums[row] == target){
            row--;
            k--;
        }

        return isValid(new int[k], row, nums, target);
    }

    private boolean isValid(int[] groups, int row, int[] nums, int target){
        if (row < 0) return true;
        int val = nums[row--];

        for (int i = 0; i < groups.length; i++){
            if (groups[i] + val <= target){
                groups[i] += val;
                if (isValid(groups, row, nums, target)) return true;
                groups[i] -= val;
            }
            if (groups[i] == 0) break;
        }

        return false;
    }
}

416 Partition Equal Subset Sum

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 > 0) return false;
        int target = sum / 2;
        int row = nums.length - 1;
        Arrays.sort(nums);

        return isValid(new int[2], row, nums, target);
    }

    private boolean isValid(int[] groups, int row, int[] nums, int target){
        if (row < 0) return true;
        int val = nums[row--];

        for (int i = 0; i < groups.length; i++){
            if (groups[i] + val <= target){
                groups[i] += val;
                if (isValid(groups, row, nums, target)) return true;
                groups[i] -= val;
            }

            if (groups[i] == 0) break;
        }

        return false;
    }
}

494 Target Sum

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        Map<String, Integer> hash = new HashMap<>();
        return dfs(nums, 0, 0, hash, S);

    }

    private int dfs(int[] nums, int index, int sum, Map<String, Integer> hash, int S){
        String encodeString = index + "->" + sum;
        if (hash.containsKey(encodeString)) return hash.get(encodeString);

        if (index == nums.length){
            if (sum == S) return 1;
            return 0;
        }

        int add = dfs(nums, index + 1, sum + nums[index], hash, S);
        int minus = dfs(nums, index + 1, sum - nums[index], hash, S);

        hash.put(encodeString, add + minus);

        return add + minus;
    }
}