Java program to calculate subset in o(n) time complexity using ArratList

1. Brutforce:

1. for(int i = 0; i < len; i++) {  
2.             //This loop adds the next character every iteration for the subset to form and add it to the array  
3.             for(int j = i; j < len; j++) {  
4.                 arr[temp] = str.substring(i, j+1);  
5.                 temp++;  
6.             }  
7.         }  

Subset can be implemented with the concept of decision tree:

How we can implement decision tree in code is:

CODE in JAVA:

	import java.sql.SQLOutput;
	import java.util.ArrayList;
	public class subset {
	static ArrayList<ArrayList<Character>> calculateSubset(String test){
	char[] charArray = test.toCharArray();
	ArrayList<ArrayList<Character>> alist = new ArrayList<ArrayList<Character>>();
	ArrayList<Character> empty = new ArrayList<>();
	alist.add(empty);
	for(char a:charArray){
	ArrayList<ArrayList<Character>> alistTemp = new ArrayList<ArrayList<Character>>();
	for(ArrayList<Character> loop :alist){
	ArrayList<Character> temp1 = new ArrayList<>();
	for(Character ch:loop){
	temp1.add(ch);
	}
	temp1.add(a);
	alistTemp.add(temp1);
	alistTemp.add(loop);
	}
	alist = alistTemp;
	}
	return alist;
	}
	public static void main(String []args){
	String test = "abcde";
	ArrayList<ArrayList<Character>> result = calculateSubset(test);
	System.out.println(result.size());
	System.out.println(result);
	}
	}

view raw subset_Java.java hosted with ❤ by GitHub