数据结构—在java中只查找求和为特定值的子集

pod7payv  于 2021-07-05  发布在  Java
关注(0)|答案(0)|浏览(175)

我有一个树状图,其中有键及其所有值和目标值。下面是我的方法。基本上就是找到一个子集。但这里我需要的是和目标值相加的键。我做了一个递归方法。这里我想结束递归,如果我得到任何一个子集。有没有最佳的方法来解决这个问题?注意:-值将更大,我将有数百个数据。

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;

    }

}

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题