Блог

У меня есть древовидная карта, в которой у меня есть ключи, все ее значения и целевое значение.Ниже приведен мой подход. В основном это поиск подмножества. Но здесь мне нужны ключи значений, которые суммируются с целью. Я применил рекурсивный подход. Здесь я хочу завершить рекурсию, если получу какое-либо одно подмножество. Есть ли какой-нибудь оптимальный способ решить эту проблему? Примечание:- Значения будут намного больше, и у меня будут сотни данных.

 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;
        
    }

}