dimanche 1 mars 2015

Java subset sum recursion



1st year CS student working on a assignment for a java subset sum problem. What i need to do output is the number of subsets equal to a target using an ArrayList that is loaded from a txt file, not the actual subsets themselves. Here is a copy of my recursion algorithm and my print out is only 61 and it should be 1845. any help would be appreciated. Thanks



public void s2() {
int d = 107;
ArrayList<Integer> s2 = new ArrayList<Integer>(file);
try {
File set2 = new File("set2.txt");
Scanner ins = new Scanner(set2);
int i = 0;
while (ins.hasNext()) {
s2.add(i, ins.nextInt());
i++;
}
ins.close();
} catch (FileNotFoundException e) {
System.out.println(e);
}
Collections.sort(s2);
file = new ArrayList<Integer>(s2);
//System.out.println(file.toString());
//for (int i = 0; i < s2.size(); i++) {
//System.out.println(i);

//echo verify it is sorted
prune(d, s2);
recDFS(d, 0, s2);
}

public void recDFS(int d, int subi, ArrayList<Integer> file) {
//System.out.println(file);
if (sum==d) {
count++;

}
for (int i = subi; i < file.size(); i++) {
if (sum+file.get(i)<=d){
subset.add(file.get(i));
sum+=file.get(i);
recDFS(d, i+1 ,file);
sum-=subset.remove(0);
}

} //System.out.println(count);
}
public void print(){
System.out.println(count);
}
}/*



Aucun commentaire:

Enregistrer un commentaire