查找重複數字的所有組合以達到給定總和

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

您可以使用地圖來保存結果。如果有重複的結果。地圖不會保存它。