package com.sunny.grokkingalgorithms.basic_2020.warmup;

import java.util.ArrayList;
import java.util.List;

public class Permutations {
	
	public static void permute(String s,String ans) {
		if(s.length() == 0) {
			System.out.print(ans + " ");			
		}
		for(int i = 0; i < s.length() ; i++) {
			char cur = s.charAt(i);
			String rest = s.substring(0, i) + s.substring(i+1);
			permute(rest,ans+cur);
		}
	}
	
	public static List<String> permute(String s) {
		if(s.length() <= 0) {
			List<String> empty = new ArrayList<String>();
			empty.add(" ");
			return empty;
		}
	    char current = s.charAt(0);
	    String remaining = s.substring(1);
	    List<String> sub = permute(remaining);
	    List<String> overall = new ArrayList<String>();
	    for(String str : sub) {
	    	//System.out.println(str);
	    	for(int i =  0; i < str.length() ; i++) {
	    		StringBuilder builder = new StringBuilder(str);
	    		builder.insert(i, current);
	    		overall.add(builder.toString());
	    	}
	    }
	    
	    overall.addAll(sub);
	    return overall;
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        String s = "abc";
        /*
         * abc
         * a  bc 
         *      b  
         *          c
         *    
         *                abcd
         *                dbacd
         *                bca
         *             
         */
        System.out.println(permute(s));
        System.out.println();
        permute(s,"");
        System.out.println();
	}

}

@@ -246,16 +246,69 @@
 %09%09%09%0A%09%09%7D%0A
+%09%09/*%0A%09%09 * ab%0A%09%09 * a %0A%09%09 *     ab%0A%09%09 *         %0A%09%09 */%0A
 %09%09for(in
@@ -429,34 +429,617 @@
 %0A%09%09%09
-permute(rest,ans+cur);%0A%09%09%7D
+//System.out.println(%22#####%22 + rest);%0A%09%09%09permute(rest,ans+cur);%0A%09%09%7D%0A%09%7D%0A%09%0A%09public static List%3CString%3E generateCombinations(String s)%7B%0A%09%09if(s.length() %3C= 0) %7B%0A%09%09%09List%3CString%3E empty = new ArrayList%3CString%3E();%0A%09%09%09empty.add(%22 %22);%0A%09%09%09return empty;%0A%09%09%7D%0A%09    char current = s.charAt(0);%0A%09    String remaining = s.substring(1);%0A%09    List%3CString%3E sub = generateCombinations(remaining);%0A%09    List%3CString%3E overall = new ArrayList%3CString%3E();%0A%09    for(String str : sub) %7B%0A%09    %09//System.out.println(str);%0A%09    %09String str1 = current + str;%0A%09    %09overall.add(str1);%0A%09    %7D%09    %0A%09    overall.addAll(sub);%0A%09    return overall;
 %0A%09%7D%0A
@@ -2143,14 +2143,97 @@
 ntln();%0A
+        System.out.println();%0A        System.out.println(generateCombinations(s));%0A
 %09%7D%0A%0A%7D%0A

Generate combinations using my approach.