Java Algorithm Question

I would convert the array to a simpler array that can be solved with your previous method, by clumping the adjacent values:

{1, 2, 2, 2, 5, 2} --> {1, 6, 5, 2}

You might want to keep some extra bookkeeping info though to be able to find the original solution from a solution to the altered problem.

This problem is similar to finding group of integers in an array which sum up to a given target.

Hint for this problem is:

The base case is when start>=nums.length. In that case, return true if target==0. Otherwise, consider the element at nums[start]. The key idea is that there are only 2 possibilities -- nums[start] is chosen or it is not. Make one recursive call to see if a solution is possible if nums[start] is chosen (subtract nums[start] from target in that call). Make another recursive call to see if a solution is possible if nums[start] is not chosen. Return true if either of the two recursive calls returns true.

You can use the same hint but with a loop in it to find sum of repeated numbers in array. Make a call to see if a solution is possible if the sum is chosen and make another call if the sum is not chosen.Return true if either of the two recursive calls returns true.

I think this would help.

public boolean groupSumClump(int start, int[] nums, int target)
{   
if(start >= nums.length) return target == 0;

int count = 1;
while(start+count < nums.length && nums[start] == nums[start+count])
count++;

if(groupSumClump(start+count, nums, target-count*nums[start])) return true;
if(groupSumClump(start+count, nums, target)) return true;

return false;
}

Once you've done missingno's preprocessing step (in linear time) what you have is essentially the subset sum problem. It's a rather hard problem, but approximate algorithms exist- might as well turn out to be practical depending on how long your sequence is.

the problem statement is ambigious and not clear:

with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group

how about choosing single digits if the 'streaks' did not work out? same example: {1,2,2,2,5,2}

in one recursive call we choose the streak of 2 2 2 (from answer above) *if(groupSumClump(start+count, nums, target-count*nums[start])) return true*

in the next rec. call why can't we subtract the first single digit at nums[start]: if(groupSumClump(start+count, nums, target)) return true;

can i do this:

if(groupSumClump(start+1, nums, target - nums[start])) return true;

DOES IT MEAN WE CAN NEVER CHOOSE SINGLE DIGITS?

Your public method parameter list for the method groupSumClump should not expose the start parameter, especially if you have an internal variable that overrides it.

Have a look at this implementation. The time complexity for the solve method is O(2^N), since in the worst case you are obliged to check all possible subsets of nums. Well unless someone proves that NP = P.

I Hope it helps.

import java.util.*;

public class SubsetSumSolver {

    public boolean solve(int[] nums, int target) {
        return solve(0, 0, target, mergeSameNumbers(nums));
    }

    private boolean solve(int start, int tempSum, int sum, ArrayList<Integer> nums) {
        if (start == nums.size())
            return sum == tempSum;
        return solve(start + 1, tempSum + nums.get(start),sum, nums) || solve(start + 1, tempSum, sum, nums);
    }

    private ArrayList<Integer> mergeSameNumbers(int[] nums) {
        if (nums.length == 0)
            return toArrayList(nums);
        LinkedList<Integer> merged = new LinkedList<>();
        int tempSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i])
                tempSum += nums[i];
            else {
                merged.add(tempSum);
                tempSum = nums[i];
            }
        }
        merged.add(tempSum);
        return new ArrayList(merged);
    }

    private ArrayList<Integer> toArrayList(int[] nums) {
        ArrayList<Integer> result = new ArrayList();
        for (int index = 0; index < nums.length; index++)
            result.add(nums[index]);
        return result;
    }

}