private void sub2 (String s, int start, List<String> tmp, int[] cut)
    {
    	if (start == s.length()) //found a match!
    	{
    		if (cut[0] == 0)
    		{
    			cut[0] = tmp.size()-1;
    		}
    		else
    		{
    			if (tmp.size()-1 < cut[0])
    			{
    				cut[0] = tmp.size()-1;
    			}
    		}
    		return;
    	}
    	
        for (int end = start + 1; end <= s.length(); ++end)
        {
            String curr = s.substring(start, end);
            if (isValid(curr, 0, curr.length()-1))
            {
            	tmp.add(curr);
            	sub2(s, end, tmp, cut);
            	tmp.remove(tmp.size()-1);
            }
        }
    }