Solution to the 'substring sum' problem (see file for a description).

SubstringSum

/**
   Solution to the 'Substring Sum' problem:
   Accept a string consisting of digits and return the number of possible groupings of digits such that
   sum of digits of each grouping at the left is less than or equal to sum of digits of every grouping on the right (i.e. they are in ascending order).
   For example:
   String = "1337"
   Groupings: "1,337"; "1,3,37"; "1,3,3,7"; "1,33,7"; "13,37"; "13,3,7"; "133,7"
   @author Sagar Ahire
 */
public class SubstringSum
{
    /**
       Solves the substring sum problem for a particular string using recursion.
       @param s A string assumed to consist of only digits
       @param leftGroup All groupings to the left of the current string 's' (Used only for printing newly discovered groups)
       @return Number of possible groups
     */
    public int findGroups(String s, String leftGroup)
    {
	int groups = 0;
	for(int i=1; i<s.length(); i++)
	{
	    if(checkSums(s, i))    // Checks if the current grouping satisfies criterion
	    {
		// Print new group
		String currLeftGroup = leftGroup == "" ? s.substring(0, i) : leftGroup + "," + s.substring(0, i);
		System.out.println(currLeftGroup + "," + s.substring(i));

		// Recurse (add 1 for this group)
		groups += 1 + findGroups(s.substring(i), currLeftGroup);
	    }
	    else    // Current grouping does not satisfy criterion. Prune this recursive tree.
		break;
	}
	return groups;
    }

    private boolean checkSums(String s, int i)
    {
	String s1 = s.substring(0, i);
	String s2 = s.substring(i);
	int sum1 = 0;
	int sum2 = 0;

	for(int j=0; j<s1.length(); j++)
	    sum1 += Integer.parseInt(s1.substring(j,j+1));
	for(int j=0; j<s2.length(); j++)
	    sum2 += Integer.parseInt(s2.substring(j,j+1));

	if(sum1 <= sum2)
	    return true;
	else
	    return false;
    }

    // Testing
    public static void main(String[] ar)
    {
	SubstringSum test = new SubstringSum();
	System.out.println("Groups for 143: " + test.findGroups("143", ""));
	System.out.println("Groups for 148: " + test.findGroups("148", ""));
	System.out.println("Groups for 1334: " + test.findGroups("1334", ""));
    }
}