Finding all possible combinations of numbers to reach a given sum Java

To write a Java method allCombinationsWithValue that determines all combinations of digits and operations that result in a specific value, you can use the following approach:

Define a helper method allCombinations that takes a list of digits and returns a Map of strings to longs, where each string represents a combination of digits and operations, and the corresponding long is the result of evaluating the combination.

1. In the allCombinations method, iterate over the list of digits and for each digit, add it to the map as a key with its value as the corresponding value.
2. For each pair of digits in the list, combine them using each of the operations (+ and -) and add the resulting combination and value to the map.
3. For each combination of three or more digits, recursively call the allCombinations method with the sublist of digits and add the resulting combinations and values to the map.
4. In the allCombinationsWithValue method, call the allCombinations method with the input list of digits and return the set of keys (combinations) that have the desired value as their corresponding value in the map.

Here is an example of how you might implement these methods in Java:

import java.util.HashMap;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

import java.util.Set;

class CombinationUtils {

  public static Set<String> allCombinationsWithValue(List<Integer> digits, int value) {

    Map<String, Long> combinations = allCombinations(digits);

    Set<String> result = new HashSet<>();

    for (Map.Entry<String, Long> entry : combinations.entrySet()) {

      if (entry.getValue() == value) {

        result.add(entry.getKey());

      }

    }

    return result;

  }

  private static Map<String, Long> allCombinations(List<Integer> digits) {

  Map<String, Long> combinations = new HashMap<>();

  for (int digit : digits) {

    combinations.put(String.valueOf(digit), (long) digit);

  }

  for (int i = 0; i < digits.size(); i++) {

    for (int j = i + 1; j < digits.size(); j++) {

      int a = digits.get(i);

      int b = digits.get(j);

      combinations.put(a + "+" + b, (long) a + b);

      combinations.put(a + "-" + b, (long) a - b);

      combinations.put(b + "-" + a, (long) b - a);

    }

  }

  for (int i = 0; i < digits.size(); i++) {

    for (int j = i + 1; j < digits.size(); j++) {

      for (int k = j + 1; k < digits.size(); k++) {

        List<Integer> sublist = digits.subList(i, k + 1);

        Map<String, Long> subcombinations = allCombinations(sublist);

        for (Map.Entry<String, Long> entry : subcombinations.entrySet()) {

          combinations.put(entry.getKey(), entry.getValue());

        }

      }

    }

  }

  return combinations;

}