查找重复数字的所有组合以达到给定总和

Question

我想查找数组中的所有组合以达到给定的总和。例如，如果阵列是[-1,1,1,2,4,4-]和给定的目标是5则应该输出是：

Expected Output 
1 1 1 2 
1 4 
1 4 

此代码是到目前为止我没有：

static void sum(int[] arr, int i, int sum, int target, String s) { 
    for (int j = i + 1; j < arr.length; j++) { 
     if (sum + arr[j] == target) { 
      System.out.println(s + " " + String.valueOf(arr[j])); 
     } else { 
      sum(arr, j, sum + arr[j], target, s + " " + String.valueOf(arr[j])); 
     } 
    } 
} 

public static void main(String[] args) { 
    int[] numbers = { 1, 1, 1, 2, 4, 4 }; 
    for (int i = 0; i < numbers.length; i++) { 
     sum(numbers, i, numbers[i], 5, String.valueOf(numbers[i])); 
    } 

} 

而且这段代码的输出是：

My Output 
1 1 1 2 
1 4 
1 4 
1 4 
1 4 
1 4 
1 4 

但是实际上，当我们有重复元素的问题，其工作的非重复数字，而不是当有重复号码。我想知道我怎么能解决这个问题，所以输出看起来像预期的那样。

Answer 1

在这个问题中我们需要处理的基本对象之一是一个Bag或MultiSet - 一组无价值的值，可以包含一个元素的多个实例。不幸的是，Java集合框架不支持这一点。我们可以用我们需要的功能编写我们自己的非常基本的版本，而不是围绕尝试让List工作。 （番石榴图书馆有一个MultiSet，所以你可以看看生产代码）。

import java.util.Map; 
import java.util.NoSuchElementException; 
import java.util.TreeMap; 

public class Bag<E> 
{ 
    private Map<E, Integer> m_values; 

    public Bag() 
    { 
     m_values = new TreeMap<E, Integer>(); 
    } 

    public Bag(Iterable<E> arr) 
    { 
     this(); 
     for(E v : arr) 
     { 
      add(v); 
     } 
    } 

    public Bag(Bag<E> b) 
    { 
     this(); 
     for(E v : b.values()) 
     { 
      set(v, b.count(v)); 
     } 
    } 

    public void add(E v) 
    { 
     Integer count = m_values.get(v); 
     m_values.put(v, count == null ? 1 : count+1); 
    } 

    public void add(Bag<E> b) 
    { 
     for(E v : b.values()) 
     { 
      Integer count = m_values.get(v); 
      m_values.put(v, count == null ? b.count(v) : count+b.count(v)); 
     } 
    } 

    public void remove(E v) 
    { 
     Integer count = m_values.get(v); 
     if(count == null) throw new NoSuchElementException(); 
     if(count == 1) 
      m_values.remove(v); 
     else 
      m_values.put(v, count-1); 
    } 

    public void remove(Bag<E> b) 
    { 
     for(E v : b.values()) 
     { 
      Integer count = m_values.get(v);  
      Integer bcount = b.count(v); 
      if(count == null || count < bcount) throw new NoSuchElementException(); 
      if(count == bcount) 
       m_values.remove(v); 
      else 
       m_values.put(v, count-bcount); 
     } 
    } 

    public boolean contains(Bag<E> b) 
    { 
     for(E v : b.values()) 
     { 
      if(count(v) < b.count(v)) return false; 
     } 
     return true; 
    } 

    public void set(E v, int count) 
    { 
     if(count == 0) 
      m_values.remove(v); 
     else 
      m_values.put(v, count); 
    } 

    public int count(E v) 
    { 
     Integer count = m_values.get(v); 
     return count == null ? 0 : count; 
    } 

    public Iterable<E> values() 
    { 
     return m_values.keySet(); 
    } 

    public String toString() 
    { 
     StringBuilder b = new StringBuilder(); 
     b.append("["); 
     for(E v : values()) 
     { 
      for(int i=0; i<count(v); i++) 
      { 
       b.append(v + " "); 
      } 
     } 
     b.deleteCharAt(b.length()-1); 
     b.append("]"); 
     return b.toString(); 
    } 
} 

在解决问题的第一步是产生候选名单将那笔5.我们可以从输入阵列生成的子集做到这一点，但我们必须要小心，不要重复包含。该代码，这是不是太糟糕，但它实际上是容易得多，如果有点效率较低，只产生你感兴趣的计数的所有可能的分区，在这种情况下，5

import java.util.ArrayList; 
import java.util.List; 

public class Partition 
{ 
    public static List<Bag<Integer>> partitions(int n) 
    { 
     return new Partition(n).partitions; 
    } 

    private List<Bag<Integer>> partitions; 
    private Bag<Integer> current; 

    private Partition(int n) 
    { 
     partitions = new ArrayList<>(); 
     current = new Bag<Integer>(); 
     build(n, n); 
    } 

    private void build(int n, int max) 
    { 
     if (n == 0) 
     { 
      partitions.add(0, new Bag<Integer>(current)); 
     } 

     for (int i = Math.min(max, n); i >= 1; i--) 
     { 
      current.add(i); 
      build(n - i, i); 
      current.remove(i); 
     } 
    } 

    public static void main(String[] args) 
    { 
     for (Bag<Integer> b : partitions(5)) 
     { 
      System.out.println(b); 
     } 
    } 
} 

输出：

[1 1 1 1 1] 
[1 1 1 2] 
[1 2 2] 
[1 1 3] 
[2 3] 
[1 4] 
[5] 

现在我们可以编写一个递归例程，从输入中提取这些分区的最大集合。唯一棘手的部分是确保当我们发现一个集合不是我们已经看到的解决方案的子集时，我们可以忽略它。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

public class Dice 
{ 
    public static List<List<Bag<Integer>>> picks(Integer[] diceArr, int k) 
    { 
     return new Dice(diceArr, k).output; 
    } 

    private List<List<Bag<Integer>>> output; 
    private List<Bag<Integer>> current; 
    private List<Bag<Integer>> partitions; 
    private Bag<Integer> dice; 

    private Dice(Integer[] diceArr, int k) 
    { 
     output = new ArrayList<>(); 
     current = new ArrayList<>(); 

     partitions = Partition.partitions(5); 
     dice = new Bag<>(Arrays.asList(diceArr)); 

     build(0); 
    } 

    private void build(int pos) 
    { 
     for (int i=pos; i<partitions.size(); i++) 
     { 
      Bag<Integer> partition = partitions.get(i); 

      if(dice.contains(partition)) 
      { 
       dice.remove(partition); 
       current.add(partition); 
       build(i); 
       current.remove(partition);    
       dice.add(partition); 
      }   
     } 

     // Only add the current list of partitions if we haven't already seen it 
     if(!current.isEmpty()) 
     { 
      boolean seen = false; 
      for(List<Bag<Integer>> prev : output) 
      { 
       if(prev.containsAll(current)) 
       { 
        seen = true; 
        break; 
       } 
      } 
      if (!seen) output.add(new ArrayList<>(current)); 
     } 
    } 

    public static void main(String[] args) 
    { 
     int count = 5; 
     Integer[] dice = {1, 1, 1, 2, 4, 4}; 
     List<List<Bag<Integer>>> picks = picks(dice, count); 
     for(List<Bag<Integer>> pick : picks) 
     { 
      System.out.println(pick); 
     } 
    } 
} 

为{1，1，1，2，4，4}输出：

[[1 1 1 2]] 
    [[1 4], [1 4]] 

输出为{1，1，1，2，3，4，4，4，5 }：

[[1 1 1 2], [5]] 
[[1 1 3], [1 4], [5]] 
[[2 3], [1 4], [1 4], [1 4], [5]] 

Answer 2

您可以使用地图来保存结果。如果有重复的结果。地图不会保存它。