Javaグループ化アルゴリズム

Question

intの配列が与えられた場合、グループに指定されたターゲットと合計するようなintのグループを選択することができます。この追加の制約は次のとおりです。同じ値であれば、それらはすべて選択されなければならないか、またはどれも選ばれていないかのいずれかでなければならない。たとえば、配列{1,2,2,2,5,2}では、中央の3つの2つをすべて選択するかどうかを選択する必要があります。 （1つのループを使用して同じ値の範囲を見つけることができます）。

テストシナリオは

groupSumClump(0, {2, 4, 8}, 10) → true true OK  
groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true true OK  
groupSumClump(0, {2, 4, 4, 8}, 14) → false false OK  
groupSumClump(0, {8, 2, 2, 1}, 9) → true false X --->Failing 
groupSumClump(0, {8, 2, 2, 1}, 11) → false false OK  
groupSumClump(0, {1}, 1) → true false X  --->Failing 
groupSumClump(0, {9}, 1) → false false OK  
other tests OK  

スニペットが

private int sum(final Integer start, final Collection<Integer> list) { 
     int sum = start; 

     for (final int i : list) { 
      sum += i; 
     } 

     return sum; 
} 

    public boolean groupSumClump(final int start, final int[] nums, final int target) {  
     for (int i = 0; i < nums.length-1; i++) { 
      if(nums[i] == nums[i+1]){//group selected logic 
      int sum = nums[i] + nums[i+1];//is this Ok ? 
      nums[i] =sum; 
      nums[i+1]=0; 
      }else{ 
      //how to handle the logic for group not selected.    
      } 
     } 

     final List<Integer> fixed = new ArrayList(); 
     final List<Integer> candidates = new ArrayList(); 

     // fills candidates and fixed 
     for (int i = 0; i < nums.length; i++) { 
      final int cand = nums[i]; 

      if (cand == 1 && i > 0) { 
       final int prev = nums[i - 1];      
      }else if (cand < target) { 
       candidates.add(cand); 
      } 
     } 

     // compute the sum of fixed 
     final int sumFixed = sum(0, fixed); 

     // if the sum of fixed is equals to target we don't need to do 
     //anything because we already know we need to return true. 
     if (sumFixed == target) { 
      return true; 
     }    
     if (sumFixed <= target && !candidates.isEmpty()) { 
     final Set<Set<Integer>> powerSets = powerSet(new HashSet(candidates));    
      for (final Set<Integer> set : powerSets) { 
       if (sumFixed + sum(0, set) == target) { 
        return true; 
       } 
      } 
     } 

     return false;   
}  

public <T> Set<Set<T>> powerSet(Set<T> originalSet) {  
     Set<Set<T>> sets = new HashSet<Set<T>>(); 
     if(originalSet.isEmpty()) { 
     sets.add(new HashSet<T>()); 
     return sets; 
     } 
List<T> list = new ArrayList<T>(originalSet); 
T head = list.get(0); 
Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
for (Set<T> set : powerSet(rest)) { 
    Set<T> newSet = new HashSet<T>(); 
    newSet.add(head); 
    newSet.addAll(set); 
    sets.add(newSet); 
    sets.add(set); 
}  
return sets; 
} 

述べたように、コードと理由の問題は、それがテストシナリオのために失敗していただきました！あなたは私を聞かせて可能性があり、以下の通りである下回っています。

私はグループのロジックが選択されていないことを知りたいですか？

Answer 1

すべてのテストケースに合格する完全なソリューションです。

それはあなたのAPIに合うようにするために自分自身を編集してください^ _^

public static void main(String[] args) { 
    int nums [] = new int[]{2, 4, 8}; 
    int target = 10; 
    int nums_another [] = grouped (nums); 
    System.out.println(viable(0, nums_another, 0, target)); 
} 

private static int [] grouped (int nums []) { 
    int nums_another[] = new int [nums.length]; 
    int i = 0; 
    int j = 0; 
    i++; 
    int c = 1; 
    while (i < nums.length){ 
     if (nums[i] == nums[i-1]) { // count identical numbers 
      c++; 
     } 
     else { // not identical, store sum of previous identical numbers (possibly only 1 number) 
      if (nums[i-1] != 0) { 
       nums_another[j] = nums[i-1] * c; 
       j++; 
      } 
      c = 1; 
     } 
     i++; 
    } 
    if (nums[i-1] != 0) { // store last 
     nums_another [j] = nums[i-1] * c; 
    } 
    return nums_another; 
} 

/* partial_sum + sub array of "array from start to 0's" -> target */ 
private static boolean viable (int partial_sum, int array[], int start, int target) { 
    if (partial_sum == target) { 
     return true; 
    } 
    else if (start >= array.length || array[start] == 0) { 
     return false; 
    } 
    else { // Key step 
     return viable (partial_sum + array[start], array, start + 1, target) 
      || viable (partial_sum,    array, start + 1, target); 
    } 
} 

キーステップ：targetはsub arrayを通じて実行可能であるかどうかを

リターン、両方のケースをテストstartが含まれるかされていません。

Answer 2

有用な第一歩は、配列をLinkedMultiSetで置き換えることです。標準的なランタイムコレクションではなく、想像力豊かで、実装を見つけたり、作成したりするのは簡単です。