Рекурсия ArrayList не учитывает повторяющиеся элементы - PullRequest
Новая
       109

Рекурсия ArrayList не учитывает повторяющиеся элементы

0 голосов
/ 08 мая 2020

У меня есть этот код, который показывает результат для достижения целевого числа, например target = 1590, но, похоже, он не учитывает кратные 3x для достижения целевого числа 

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

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {431, 431, 429, 427, 424, 422, 420, 418, 416, 414, 412,
    409, 407, 405, 403, 401, 398, 396, 394, 392, 389, 409, 347, 347, 344, 344, 342, 342,
    339, 342, 344, 347, 349, 352, 354, 357, 359, 361, 364, 364, 364, 364, 431, 451, 449, 447,
    445, 443, 441, 439, 437, 435, 433, 431, 429, 427, 424, 422, 420, 418, 416, 414, 412};
        int target = 1590;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Для примера output, sum ([431, 424, 396, 339]) = 1590, но он не учитывает 3x комбо, подобное этой [424, 392, 392, 392] также = 1590

Как бы мне go о пересчете элементов для достижения целевого числа?

1 Ответ

0 голосов
/ 08 мая 2020

Вы не должны строить remaining из i+1, так как это исключает дубликаты. Вместо этого вы можете начать с 0. Однако таким образом вы создадите дубликаты, которые вам придется дедуплицировать. Вы можете поступить следующим образом: 

class SumSet {
  static void sum_up_recursive(List<Integer> numbers, int target, List<Integer> partial, Set<List<Integer>> resultSet) {
    int s = 0;
    for (int x: partial) {
      s += x;
    }
    if (s == target) {
      // Deduplication of results
      Collections.sort(partial);
      resultSet.add(partial);
    }
    if (s >= target) {
      return;
    }
    for (int i = 0; i < numbers.size(); i++) {
      int n = numbers.get(i);
      List<Integer> partial_rec = new ArrayList<>(partial);
      partial_rec.add(n);
      sum_up_recursive(numbers, target, partial_rec, resultSet);
    }
  }
  static void sum_up(List<Integer> numbers, int target) {
    final Set<List<Integer>> resultSet = new HashSet<>();
    sum_up_recursive(numbers, target, new ArrayList<>(), resultSet);
    for (List<Integer> result : resultSet) {
      System.out.println("sum("+Arrays.toString(result.toArray())+")="+target);
    }

  }
  public static void main(String args[]) {
    Integer[] numbers = {431, 431, 429, 427, 424, 422, 420, 418, 416, 414, 412,
        409, 407, 405, 403, 401, 398, 396, 394, 392, 389, 409, 347, 347, 344, 344, 342, 342,
        339, 342, 344, 347, 349, 352, 354, 357, 359, 361, 364, 364, 364, 364, 431, 451, 449, 447,
        445, 443, 441, 439, 437, 435, 433, 431, 429, 427, 424, 422, 420, 418, 416, 414, 412};
    int target = 1590;
    sum_up(new ArrayList<>(Arrays.asList(numbers)),target);
  }
...