示例：
input = [2, 3, 3, 4, 5]
sumTargets = [8, 6, 3]
我想要一种算法将
inputinputsumTargets[ [3, 5], [2, 4], [3] ]
我过去见过更简单的子集问题，所以想到使用递归来遵循类似的方法，但我使用了两种递归方法，而且它变得混乱。在我继续深入兔子洞之前，我想知道是否有更简单的方法？
这是我的解决方案：
package stackoverflow;
import java.util.ArrayList;
import java.util.Collection;
import jc.lib.collection.map.JcMultiMap;
import jc.lib.math.permutation.JcUSubset;
public class SumTuple {
public static void main(final String... args) {
final int[] input = { 2, 3, 3, 4, 5 };
final int[] sumTargets = { 8, 6, 3 };
// convert int[] to Integer[]
final Integer[] inputRefs = new Integer[input.length];
for (int i = 0; i < input.length; i++) {
inputRefs[i] = Integer.valueOf(input[i]);
}
// build multimap: sum -> arraylists
final ArrayList<ArrayList<Integer>> subset = JcUSubset.getSubsets(inputRefs);
final JcMultiMap<Integer, ArrayList<Integer>> mmap = new JcMultiMap<>();
for (final ArrayList<Integer> ss : subset) {
final Integer sum = getSum(ss); // we could optimize a bit here: if sum > max(sumTargets), we just drop it. or we could even tune that check into JcUSubset, if performance is key
mmap.put(sum, ss);
}
// get combinations for values
System.out.println("Solutions:");
for (final int st : sumTargets) {
final Integer key = Integer.valueOf(st);
final Collection<ArrayList<Integer>> values = mmap.getValues(key);
System.out.println("For value [" + st + "]:");
for (final ArrayList<Integer> vs : values) {
System.out.print("\t");
for (final Integer v : vs) {
System.out.print(v + " ");
}
System.out.println();
}
}
// fyi print all combinations+sums available
System.out.println("\nAll combinations:");
for (final Integer key : mmap.getAllKeys()) {
System.out.println("\tKey: " + key);
final Collection<ArrayList<Integer>> values = mmap.getValues(key);
for (final ArrayList<Integer> vs : values) {
System.out.print("\t\t");
for (final Integer v : vs) {
System.out.print(v + " ");
}
System.out.println();
}
}
}
static private Integer getSum(final ArrayList<Integer> pSubSet) {
int acc = 0;
for (final Integer i : pSubSet) {
if (i != null) acc += i.intValue();
}
return Integer.valueOf(acc);
}
}
与 JcUSubset 类
package jc.lib.math.permutation;
import java.util.ArrayList;
public final class JcUSubset {
private JcUSubset() {}
@SafeVarargs static public <T> ArrayList<ArrayList<T>> getSubsets(final T... pItems) {
final int n = pItems.length;
final boolean[] indices = new boolean[n];
final ArrayList<ArrayList<T>> ret = new ArrayList<>();
final int max = (int) Math.pow(2, n);
for (int i = 0; i < max; i++) {
final ArrayList<T> list = new ArrayList<>(n);
for (int j = 0; j < indices.length; j++) {
if (indices[j]) list.add(pItems[j]);
}
ret.add(list);
increment(indices);
}
return ret;
}
static private void increment(final boolean[] pIndices) {
for (int i = pIndices.length - 1; i >= 0; i--) {
if (pIndices[i] == false) {
pIndices[i] = true;
break;
} else {
pIndices[i] = false;
}
}
}
public static void main(final String[] args) {
final String[] t1 = { "1", "2", "3" };
final ArrayList<ArrayList<String>> perms = getSubsets(t1);
System.out.println("Perms: ");
for (final ArrayList<String> strings : perms) {
System.out.print("\t");
for (final String s : strings) {
System.out.print(s + " ");
}
System.out.println();
}
System.out.println("Done.");
}
}
和 JcMultiMap 类：
package jc.lib.collection.map;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.Supplier;
import jc.lib.container.collection.list.array.JcArrayList;
import jc.lib.container.iterable.JcUIterable;
import jc.lib.java.lang.exceptions.implementation.notimplemented.JcXNotImplementedMethodException;
import jc.lib.lang.string.JcUStringBuilder;
/**
* A map that holds multiple values in collections for the same key.<br>
* <br>
* Depending on the implemented collection, multiple equal entries per list are possible.<br>
* The default collection creation lambda created {@linkplain ArrayList}s.<br>
* Set the creation lambda for the collection by calling {@link #setCollectionCreationLambda(Supplier)}<br>
* <br>
* Backing map is {@linkplain HashMap}, but can be set to any {@linkplain Map} implementation on initialization.
*
* @author JayC667
*/
public class JcMultiMap<K, V> implements Iterable<Collection<V>>, Serializable, Map<K, V> {
private static final long serialVersionUID = -5957723898350358328L;
private final Map<K, Collection<V>> mMap;
private Supplier<Collection<V>> mCollectionCreationLambda = () -> new ArrayList<>();
public JcMultiMap(final Map<K, Collection<V>> pBackingMap) {
mMap = pBackingMap;
}
public JcMultiMap(final boolean pTreeBackingMap) {
this(pTreeBackingMap ? new TreeMap<>() : new HashMap<>());
}
public JcMultiMap() {
this(false);
}
public void setCollectionCreationLambda(final Supplier<Collection<V>> pCollectionCreationLambda) {
mCollectionCreationLambda = pCollectionCreationLambda;
}
private Collection<V> getListFor(final K pKey) {
Collection<V> list = mMap.get(pKey);
if (list == null) {
list = mCollectionCreationLambda.get();
mMap.put(pKey, list);
}
return list;
}
@Override public V put(final K pKey, final V pValue) {
final Collection<V> list = getListFor(pKey);
list.add(pValue);
return null;
}
public V putUnique(final K pKey, final V pValue) {
final Collection<V> list = getListFor(pKey);
if (!list.contains(pValue)) list.add(pValue);
return null;
}
public V putAll(final K pKey, final Iterable<V> pValues) {
final Collection<V> list = getListFor(pKey);
for (final V v : pValues) {
list.add(v);
}
return null;
}
public V putAll(final K pKey, @SuppressWarnings("unchecked") final V... pValues) {
final Collection<V> list = getListFor(pKey);
if (pValues != null) {
for (final V v : pValues) {
list.add(v);
}
}
return null;
}
// public V get(final K pKey) {
// final JcList<V> list = mMap.get(pKey);
// if (list == null || list.getItemCount() == 0) return null;
// return mMap.get(pKey).get(0);
// }
public Collection<V> getValues(final K pKey) {
return mMap.get(pKey);
}
public HashSet<V> getUniqueValues(final K pKey) {
final Collection<V> list = mMap.get(pKey);
if (list == null) return new HashSet<>();
return new HashSet<>(list);
}
public V getFirstValue(final K pKey) {
final Collection<V> list = getValues(pKey);
if (list == null || list.size() < 1) return null;
return JcUIterable._getFirst(list);
}
public Set<K> getAllKeys() {
return mMap.keySet();
}
public JcArrayList<V> getAllValues() {
final JcArrayList<V> ret = new JcArrayList<>();
for (final Collection<V> list : mMap.values()) {
ret.addItems(list);
}
return ret;
}
public void removeAllItems() {
mMap.clear();
}
@Override public Iterator<Collection<V>> iterator() {
return mMap.values().iterator();
}
@Override public String toString() {
final StringBuilder sb = new StringBuilder();
for (final K key : mMap.keySet()) {
sb.append(key + ": [");
final Collection<V> values = getValues(key);
sb.append(JcUStringBuilder.buildFromIterable(", ", values));
sb.append("]\n");
}
if (sb.length() > 1) sb.setLength(sb.length() - 1);
return sb.toString();
}
public int getItemCount() {
int counter = 0;
for (final Collection<V> x : mMap.values()) {
counter += x.size();
}
return counter;
}
public void removeKey(final K pHash) {
mMap.remove(pHash);
}
public void removeItem(final K pKey, final V pItem) {
final Collection<V> values = mMap.get(pKey);
if (values != null) values.remove(pItem);
}
@Override public void clear() {
mMap.clear();
}
/**
* @deprecated Use {@link #getAllValues()} instead!
*/
@Deprecated @Override public Set<java.util.Map.Entry<K, V>> entrySet() {
throw new JcXNotImplementedMethodException();
}
@Deprecated @Override public V get(final Object pArg0) {
throw new JcXNotImplementedMethodException();
}
@Override public boolean isEmpty() {
return mMap.isEmpty();
}
@Override public Set<K> keySet() {
return mMap.keySet();
}
@Deprecated @Override public void putAll(final Map<? extends K, ? extends V> pArg0) {
throw new JcXNotImplementedMethodException();
}
@SuppressWarnings("unlikely-arg-type") @Override public V remove(final Object pArg0) {
mMap.remove(pArg0);
return null;
}
@Override public int size() {
return mMap.size();
}
@Deprecated @Override public Collection<V> values() {
throw new JcXNotImplementedMethodException();
}
@SuppressWarnings("unlikely-arg-type") @Override public boolean containsKey(final Object pKey) {
return mMap.containsKey(pKey);
}
@Override public boolean containsValue(final Object pValue) {
for (final Collection<V> q : mMap.values()) {
for (final V v : q) {
if (pValue.equals(v)) return true;
}
}
return false;
}
/**
* Use {@link #removeItem(Object, Object)} instead!
*/
@Override @Deprecated public boolean remove(final Object key, final Object value) {
throw new JcXNotImplementedMethodException();
}
}
示例中未使用其中引用的其他类。您只需将它们注释掉即可。