recursion3.java

import java.util.*;//for unique string in subsequences

public class recursion3 {
    //subsequences: possible combination but in order it is in the string itself
    public static void subSequences(String str, int idx, String newString){
        if(idx==str.length()){
            System.out.println(newString);
            return;
        }
        char current=str.charAt(idx);
        //to be in
        subSequences(str, idx+1, newString+current);
        //not to be in
        subSequences(str, idx+1, newString);
    }
        public static void subSequencesUni(String str1, int idx, String newString, HashSet<String> set){
            if(idx==str1.length()){
                if(set.contains(newString)){
                    return;
                }else{
                System.out.println(newString);
                set.add(newString);
                return;
                }
            }
            char current=str1.charAt(idx);
            //to be in
            subSequencesUni(str1, idx+1, newString+current, set);
            //not to be in
            subSequencesUni(str1, idx+1, newString,set);
        }
    public static String keypad[]={"0","abc","def","ghi","jkl","mno","pqrs","tu","vw","xyz"};
    public static void combinations(int idx, String str2, String combina){
        if (idx==str2.length()){
            System.out.println(combina);
            return;
        }
        char current=str2.charAt(idx);
        String mapping=keypad[current-'0'];
        for (int i=0; i<mapping.length();i++){
            combinations(idx+1, str2, combina+mapping.charAt(i));
        }
    }
    //permutations : all posible combinations but length is equal to length of the given string no repetation not in order
    public static void permutations(String str, String perm){
        if(str.length()==0){
            System.out.println(perm);
            return;
        }
        for (int i=0;i<str.length();i++){
             char current=str.charAt(i);
             String newString=str.substring(0, i)+str.substring(i+1);
             permutations(newString, perm+current);
        }
    }
    //reach from (0,0) to (n,m) in a matrix by how many paths we can go only right and downwards
    public static int countPath(int i,int j,int n, int m){
        if (i==n || j==m){
            return 0;
        }
        if(i==n-1 && j==m-1){
            return 1;
        }
        //move downwards
        int downpath=countPath(i+1, j, n, m);
        //move right
        int rightpath=countPath(i, j+1, n, m);
        return downpath+rightpath;
    }
    public static void main(String args[]){
    String str="abc";
    subSequences(str, 0, "");
    String str1="aaa";
    HashSet<String> set=new HashSet<>();
    subSequencesUni(str1, 0, "", set);  
    Scanner sc=new Scanner(System.in);
    String str2=sc.next();
    combinations(0, str2, "");  
    permutations(str, "");
    int n=3, m=3;
    int totalpath=countPath(0, 0, n, m);
    System.out.println(totalpath);
    }
    
}