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; } }