Return to Answer

// this method should return all possible numbers in a string
// of digits. For "1234" it should return {1,2,3,4,12,23,34,123,234}
int[] getPossibleNumbers(String digits){
    char[] chars = digits.toCharArray();
    List<int> numbers = new List<int>();
    int helper;
    int zero = 48; // this is the char val for the '0' digit

    for(int i = 0; i < chars.length; i++){
        for(int j = 1; j < chars.length && (i + j) < chars.length; j++){
            helper = 0;

            for(int k = 0; k < j; k++){
                helper = (helper * 10) + ((int)chars[i + k]) - zero;
            }

            numbers.append(helper);
        }
    }

    return numbers.toArray();
}

int minSums(String digits, int sum){
    int[] numbers = getPossibleNumbers(digits);
    Queue<SumStatus> backupQueue = new Queue<SumStatus>();
    int numbersStartingIndex; // this index will be used to get the various numbers to sum

    for(int i = 0; i < numbers.length; i++){
        SumStatus status = new SumStatus(new List<int>().append(numbers[i]), numbers[i]);
        backupQueue.push(status);
    }

    while(!backupQueue.isEmpty()){
        SumStatus status = backupQueue.pop();

        if(status.sum == sum){
            // we found the min-sum
            return status.numbers.length() - 1;
        }

        if(status.sum < sum){
            // we have not found the min-sum yet
            numbersStartingIndex = status.numbers.length();
            for(int i = numbersStartingIndex; i < numbers.length; i++){
                SumStatus newStatus = new SumStatus(status.numbers, status.sum);
                newStatus.numbers.append(numbers[i]);
                newStatus.sum += numbers[i];

                if(newStatus.sum <= sum){
                    backupQueue.push(status);
                }
            }
        }

        // when status.sum > sum the item is simply ignored and popped from the queue
    }

    // no possible combination found
    return -1;
}

class SumStatus{
    List<int> numbers;
    int sum;

    SumStatus(List<int> nums, int currentSum){
        numbers = nums;
        sum = currentSum;
    }
}

The proposed solution does a Breadth-First Search in the State Space of the problem. The State Space is made of the numbers evaluated till that moment. The Breadth-First Search may not be immediatly visible because there's no tree to visit in a recursive fashion, but it's implemented via a Queue<SumStatus>.

// this method should return all possible numbers in a string
// of digits. For "1234" it should return {1,2,3,4,12,23,34,123,234}
int[] getPossibleNumbers(String digits){
    char[] chars = digits.toCharArray();
    List<int> numbers = new List<int>();
    int helper;
    int zero = 48; // this is the char val for the '0' digit

    for(int i = 0; i < chars.length; i++){
        for(int j = 1; j < chars.length && (i + j) < chars.length; j++){
            helper = 0;

            for(int k = 0; k < j; k++){
                helper = (helper * 10) + ((int)chars[i + k]) - zero;
            }

            numbers.append(helper);
        }
    }

    return numbers.toArray();
}

int minSums(String digits, int sum){
    int[] numbers = getPossibleNumbers(digits);
    Queue<SumStatus> backupQueue = new Queue<SumStatus>();
    int numbersStartingIndex; // this index will be used to get the various numbers to sum

    for(int i = 0; i < numbers.length; i++){
        SumStatus status = new SumStatus(new List<int>().append(numbers[i]), numbers[i]);
        backupQueue.push(status);
    }

    while(!backupQueue.isEmpty()){
        SumStatus status = backupQueue.pop();

        if(status.sum == sum){
            // we found the min-sum
            return status.numbers.length() - 1;
        }

        if(status.sum < sum){
            // we have not found the min-sum yet
 
            if(status.availableNumbers.length > 0){
                for(int i = 0; i < status.availableNumbers.length; i++){
                    SumStatus newStatus = new SumStatus(status.numbers, status.sum);
                    newStatus.numbers.append(status.availableNumbers[i]);
                    newStatus.sum += status.availableNumbers[i];
                    // copy the new available numbers (all the previously available ones except for the one in position 'i')
                    newStatus.availableNumbers = CopyArray(status.availableNumbers, exceptIndex: i);

                    if(newStatus.sum <= sum){
                        backupQueue.push(status);
                    }
                }
            }
        }

        // when status.sum > sum the item is simply ignored and popped from the queue
    }

    // no possible combination found
    return -1;
}

class SumStatus{
    List<int> numbers;
    int[] availableNumbers;
    int sum;

    SumStatus(List<int> nums, int currentSum){
        numbers = nums;
        sum = currentSum;
    }
}

The proposed solution does a Breadth-First Search in the State Space of the problem. The State Space is made of: the numbers evaluated up to that state, the sum of the used numbers, and the available numbers (the ones not yet used). The Breadth-First Search may not be immediatly visible because there's no tree to visit in a recursive fashion, but it's implemented via a Queue<SumStatus>.

P.S.: The code is not functional code. It just serves as a means to clarify the idea I had.

P.S.: The code is not working code. It just serves as a means to clarify the idea I had.

// this method should return all possible numbers in a string
// of digits. For "1234" it should return {1,2,3,4,12,23,34,123,234}
int[] getPossibleNumbers(String digits){
    char[] chars = digits.toCharArray();
    List<int> numbers = new List<int>();
    int helper;
    int zero = 48; // this is the char val for the '0' digit

    for(int i = 0; i < chars.length; i++){
        for(int j = 1; j < chars.length; j++){
            helper = 0;

            for(int k = 0; k < j && (i + k) < chars.length; k++){
                helper = (helper * 10) + ((int)chars[i + k]) - zero;
            }

            numbers.append(helper);
        }
    }

    return numbers.toArray();
}

int minSums(String digits, int sum){
    int[] numbers = getPossibleNumbers(digits);
    Queue<SumStatus> backupQueue = new Queue<SumStatus>();
    int numbersStartingIndex; // this index will be used to get the various numbers to sum

    for(int i = 0; i < numbers.length; i++){
        SumStatus status = new SumStatus(new List<int>().append(numbers[i]), numbers[i]);
        backupQueue.push(status);
    }

    while(!backupQueue.isEmpty()){
        SumStatus status = backupQueue.pop();

        if(status.sum == sum){
            // we found the min-sum
            return status.numbers.length() - 1;
        }

        if(status.sum < sum){
            // we have not found the min-sum yet
            numbersStartingIndex = status.numbers.length();
            for(int i = numbersStartingIndex; i < numbers.length; i++){
                SumStatus newStatus = new SumStatus(status.numbers, status.sum);
                newStatus.numbers.append(numbers[i]);
                newStatus.sum += numbers[i];

                if(newStatus.sum <= sum){
                    backupQueue.push(status);
                }
            }
        }

        // when status.sum > sum the item is simply ignored and popped from the queue
    }

    // no possible combination found
    return -1;
}

class SumStatus{
    List<int> numbers;
    int sum;

    SumStatus(List<int> nums, int currentSum){
        numbers = nums;
        sum = currentSum;
    }
}

// this method should return all possible numbers in a string
// of digits. For "1234" it should return {1,2,3,4,12,23,34,123,234}
int[] getPossibleNumbers(String digits){
    char[] chars = digits.toCharArray();
    List<int> numbers = new List<int>();
    int helper;
    int zero = 48; // this is the char val for the '0' digit

    for(int i = 0; i < chars.length; i++){
        for(int j = 1; j < chars.length && (i + j) < chars.length; j++){
            helper = 0;

            for(int k = 0; k < j; k++){
                helper = (helper * 10) + ((int)chars[i + k]) - zero;
            }

            numbers.append(helper);
        }
    }

    return numbers.toArray();
}

int minSums(String digits, int sum){
    int[] numbers = getPossibleNumbers(digits);
    Queue<SumStatus> backupQueue = new Queue<SumStatus>();
    int numbersStartingIndex; // this index will be used to get the various numbers to sum

    for(int i = 0; i < numbers.length; i++){
        SumStatus status = new SumStatus(new List<int>().append(numbers[i]), numbers[i]);
        backupQueue.push(status);
    }

    while(!backupQueue.isEmpty()){
        SumStatus status = backupQueue.pop();

        if(status.sum == sum){
            // we found the min-sum
            return status.numbers.length() - 1;
        }

        if(status.sum < sum){
            // we have not found the min-sum yet
            numbersStartingIndex = status.numbers.length();
            for(int i = numbersStartingIndex; i < numbers.length; i++){
                SumStatus newStatus = new SumStatus(status.numbers, status.sum);
                newStatus.numbers.append(numbers[i]);
                newStatus.sum += numbers[i];

                if(newStatus.sum <= sum){
                    backupQueue.push(status);
                }
            }
        }

        // when status.sum > sum the item is simply ignored and popped from the queue
    }

    // no possible combination found
    return -1;
}

class SumStatus{
    List<int> numbers;
    int sum;

    SumStatus(List<int> nums, int currentSum){
        numbers = nums;
        sum = currentSum;
    }
}