Поиск всех подмножеств, суммирующих n, с помощью обратного отслеживания

Question

Я хочу найти все целочисленные подмножества, которые суммируют n с помощью обратного отслеживания

Например, для целых:

1 2 3 4 5 6 7

и n = 7

Я хочуouput

1 2 4
1 6
2 5
3 4
7 

Я думаю, что я должен передать позицию в массиве целых чисел, которую я оцениваю как аргумент, но я застрял в написании остальной логики.

Мой код пока:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 *
 * @author talleres
 */
public class Main {




int sum (TreeSet<Integer>ts, int temp) {

    int sum=0;

    for (Integer i: ts){

        sum +=i;

    }

    return sum+temp;
}



static HashSet<TreeSet<Integer>> alternatives = new HashSet <TreeSet<Integer>>();
static ArrayList<TreeSet<Integer>> subsets = new ArrayList <TreeSet<Integer>>();

static TreeSet<Integer> getNextSubset (){

    TreeSet<Integer> alternative = new TreeSet<Integer>();

    if (!alternatives.contains(alternative)){   
        return alternative;   
    }
    else return null; // BEWARE!! 
} 

static void findSubsets (ArrayList<Integer> numbers, int amount, int index){


    TreeSet <Integer> subset = new TreeSet<Integer>();

    int temp = numbers.get(index); //initialize alternative

    if (temp<=amount)
        subset.add(temp);

    if (temp==amount)
        subsets.add(subset);




}


    public static void main(String[] args) throws IOException {
        // TODO code application logic here

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("inset integers");

        ArrayList<Integer> numeros = new ArrayList<Integer>();
        String line=br.readLine();

        while (!line.equals("")){
            numeros.add (Integer.parseInt(line));
            line = br.readLine();
        }

        Collections.sort(numeros);

        System.out.println("insert the amount the subsets should sum");
           line = br.readLine();

        int amount = Integer.parseInt(line);

        ArrayList<Integer> accum = new ArrayList<Integer>();

        findSubsets(numeros, amount, 0);


    }

}

Answer 1

Вот некоторый псевдокод, с которым вы можете работать:

Set<Set<Integer>> subsets(Set<Integer> remaining, int n) {
    results = new HashSet<Set<Integer>>();

    if (n == 0)
        results.add(empty set);

    for each i in remaining
        newRemaining = remaining \ {i}

        for each subresult in subsets(newRemaining, n - i)
            results.add(subresult + {i})

    return results
}

Должен работать и для отрицательных чисел.(хм, на самом деле будет работать. Я реализовал это и протестировал перед написанием псевдокода: -)

Answer 2

У меня может возникнуть соблазн сделать это в рекурсивной функции. Это кажется простым. Это может быть не самым лучшим, но это будет хорошо работать.

Это очень много в псевдокоде и предполагает, что числа равны 1..END. Если вы получили список, то вам следует отсортировать, а затем использовать список [i].

find(int curpos,int cursum,int sumleft,char output[])
{
  if (sumleft == 0)
   print(output);
  if (curpos > sumleft)
   return;
  for(i=curpos;i<=TARGET && i<=sumleft)
    find(i+1,cursum+i,sumleft-i,output+i."+%d")
}

main()
{
  char output[100];
  find(1,0,TARGET,"");
}