Combination Misc

Generate all combination which prints star in place of absent characters
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/CombinationWithStar.java
    public void combine(char input[], int pos, boolean used[]){
        printArray(input, used);
        for(int i= pos; i < input.length; i++){
            used[i] = true;
            combine(input, i+1, used);
            used[i] = false;
        }
    }
 
    private void printArray(char result[], boolean used[]){
        for(int i=0; i < used.length; i++){
            if(used[i]){
                System.out.print(result[i] + " ");
            }else{
                System.out.print("* ");
            }
        }
        System.out.println();
    }
Combination with repetition of characters allowed
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/CombinationWithReptition.java
    public void combination(char input[],int count[]){
        int len =0;
        for(int i=0; i < count.length; i++){
            len += count[i];
        }
        char result[] = new char[len];
        combination(input,count,0,0,result,0);
    }
 
    private void combination(char input[],int count[],int pos, int countPos, char result[],int len){
     
        if(pos == input.length){
            return;
        }
        print(result,len);
        for(int i=pos; i < input.length; i++){
            if(countPos < count[i]){
                result[len] = input[i];
                combination(input,count,i,countPos+1,result,len+1);
            }
            countPos = 0;
        }
    }
 
    public void combination(char input[]){
        Arrays.sort(input);
        char result[] = new char[input.length];
        combination(input,0,result,0);
    }
 
    private void combination(char input[],int pos,char result[],int len){
        print(result,len);
        for(int i=pos; i < input.length;)
        {
            //idea is to find first non repeated char position j.
            // then keep adding one element from repetition and find combination for
            //rest of the array
            //e.g aaabbc i = 0 j = 3 we do a{bbc} then aa{bbc} aaa{bbc}
            int j= i;
            while(j < input.length && input[i] == input[j]){
                j++;
            }
            int tempLen = len;
            for(int k=i; k < j; k++){
                result[len] = input[i];
                combination(input,j,result,len+1);
                len++;
            }
            len = tempLen;
            i = j;
        }
    }
 
    private void print(char result[],int pos){
        for(int i=0; i < pos; i++){
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintPermInSortedOrder.java
    public void printPerm(char arr[], int current, boolean used[],char []result){
     
        if(current == arr.length){
            printArray(result);
        }
        for(int i=0; i < arr.length; i++){
            if(!used[i]){
                used[i] = true;
                result[current] = arr[i];
                printPerm(arr, current+1, used,result);
                used[i] = false;
            }
        }
     
    }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/StringPermutationRotation.java
    public void permute(char[] str,int pos){
        if(pos == str.length){
            printArray(str);
            return;
        }
        for(int i=pos; i < str.length; i++){
            swap(str,pos,i);
            permute(str,pos+1);
            swap(str,pos,i);
        }
    }
Given an input and total, print all combinations with repetitions in this input which sums to given total.
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintSumCombination.java
  private void print(int input[], int sum, List<Integer >result) {  
      if(sum < 0) {
          return;
      }
      if(sum == 0) {
          result.stream().forEach(i -> System.out.print(i + " "));
          System.out.println();
          return;
      }
   
   
      for(int i=0; i < input.length; i++) {
          result.add(input[i]);
          print(input, sum - input[i], result);
          result.remove(result.size()-1);
      }
  }
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/WordCombination.java
 * Given a list of list of Strings. Print cartesian product of lists.
 * input -> {"Hello", "World"} , {"Game"}, {"Go","Home"}
 * output ->
 * Hello Game Go
 * Hellow Game Home
 * World Game Go
 * World Game Home
    public void printCombinations(List<List<String>> input) {
        int[] result = new int[input.size()];
        print(input,result, 0);
    }

    private void print(List<List<String>> input, int[] result, int pos) {

        if(pos == result.length){
            for (int i = 0; i < input.size(); i++) {
                System.out.print(input.get(i).get(result[i]) + " ");
            }
            System.out.println();
            return;
        }

        for(int i=0; i < input.get(pos).size(); i++){
            result[pos] = i;
            print(input,result, pos+1);

        }
    }
Given two strings, generate all interleavings of these strings
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/StringInterleaving.java
    public void interleaving(char[] str1,char[] str2,int len1,int len2,int current, char []result){
       
        if(current == result.length){
            printArray(result);
            return;
        }

        if(len1 < str1.length){
            result[current] = str1[len1];
            interleaving(str1, str2, len1+1, len2, current+1, result);
        }
        if(len2 < str2.length){
            result[current] = str2[len2];
            interleaving(str1,str2,len1,len2+1,current+1,result);
        }
    }
        char[] result = new char[str1.length() + str2.length()];
        si.interleaving(str1.toCharArray(), str2.toCharArray(), 0, 0, 0, result);  
Generate all possible string combinations of a given phone number
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/KeyPadPermutation.java
    private void permute(int input[], int pos, char result[]) {
        if (pos == input.length) {
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]);
            }
            System.out.println();
            return;
        }

        char[] str = getCharSetForNumber(input[pos]);
        for (char ch : str) {
            result[pos] = ch;
            permute(input, pos+1, result);
        }
    }

    private char[] getCharSetForNumber(int num) {
        switch(num){
            case 1 : return "abc".toCharArray();
            case 2 : return "def".toCharArray();
            case 3: return "ghi".toCharArray();
            case 4: return "jkl".toCharArray();
            case 5: return "mno".toCharArray();
            case 6: return "pqrs".toCharArray();
            case 8: return "tuv".toCharArray();
            case 9: return "wxyz".toCharArray();
        }
        throw new IllegalArgumentException();
    }