我有一个树状图,其中有键及其所有值和目标值。下面是我的方法。基本上就是找到一个子集。但这里我需要的是和目标值相加的键。我做了一个递归方法。这里我想结束递归,如果我得到任何一个子集。有没有最佳的方法来解决这个问题?注意:-值将更大,我将有数百个数据。
import java.util.*;
public class SubsetFromATree {
public static void main(String[] args) {
TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>() ;
tm.put(0, 3);
tm.put(1, 4);
tm.put(2, 5);
tm.put(3, 6);
// for(int i =0;i<20;i++) {
// tm.put(i, i+1);
// }
ArrayList<Integer> ans = new ArrayList<>();
ArrayList<Integer> out = new ArrayList<>();
StringBuffer s = new StringBuffer("0");
subset(tm,10,out,tm.size(),s,ans);
System.out.println(ans);
}
private static void subset(TreeMap<Integer, Integer> tm, int tsum, ArrayList<Integer> out, int size, StringBuffer val,
ArrayList<Integer> ans) {
// TODO Auto-generated method stub
if(tsum == 0) {
val.append("1");
for(int i = 0;i<out.size();i++) {
ans.add(out.get(i));
}
return;
}
if(size == 0 || val.equals("1")) {
return;
}
//Not including
subset(tm,tsum,out,size-1,val,ans);
ArrayList<Integer> output = new ArrayList<>(out);
output.add(tm.get(size-1));
subset(tm,tsum-tm.get(size-1),output,size-1,val,ans);
return;
}
}
暂无答案!
目前还没有任何答案,快来回答吧!