Recursive depth first search Integer ArrayList Java

601 views Asked by At

What I'm trying to do is essentially look at a set of numbers, and find all subsets of those numbers and eventually print them out. I'm completely stuck on writing the recursion method. The idea is to use a Boolean arraylist as a form of a tree, and traverse through it testing all the different sums for what I'm looking for. The problem is that it's not even going through the tree correctly, so any suggestions would be of great help.

package programmingassignment3;
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class SubsetSum {

    public ArrayList<Integer> set1 = new ArrayList<Integer>(Arrays.asList(1,2,3,4));
    int d = 6;

    public void  test(){
        Collections.sort(set1);
        for(int i =0;i<set1.size();i++)
            if(set1.get(i)>d)
                set1.remove(i);
        ArrayList<Boolean> set1test = new ArrayList();
        recSubSetSum(set1test); 
    }


    public void recSubSetSum(ArrayList<Boolean> subsetList)
    {

        if(sumOfList(subsetList)>=d)
            System.out.println("Output Set(WIP)");
        ArrayList<Boolean> leftList = new ArrayList();
        ArrayList<Boolean> rightList = new ArrayList();
        for(int i =0;i<set1.size();i++)
        {
            leftList = new ArrayList(subsetList);
            rightList = new ArrayList(subsetList);
            if(set1.size()>leftList.size())
                leftList.add(true);
            if(set1.size()>rightList.size())
                rightList.add(false);

            if(sumOfList(leftList)<d)
            {
                recSubSetSum(leftList);
                if(set1.size()>rightList.size())
                    rightList.add(false);
            }
            if(sumOfList(rightList)<d)
                recSubSetSum(rightList);
        }
    }

    public int sumOfList(ArrayList<Boolean> subSetList)
    {
        int sum = 0;

        for(int i = 0;i<subSetList.size();i++)
        {

            if(subSetList.get(i))
                sum+=set1.get(i);
        }
        return sum;
    }
}
0

There are 0 answers