Recursive

Print all the possible combination of given string

Pinterest LinkedIn Tumblr

Write a program to print all the possible combination of given string.

source Code

package com.dsacode.Algorithm.recursive;
 
public class AllPossiblecombinations {
     
        private StringBuilder output = new StringBuilder();
         
        private final String inputstring;
         
        public AllPossiblecombinations( final String str ){
            inputstring = str;
            System.out.println("The input string  is  : " + inputstring);
        }
         
        public void combine() {
            combine( 0 );
        }
         
        private void combine(int start ){
            for( int i = start; i < inputstring.length(); ++i ){
                output.append( inputstring.charAt(i) );
                System.out.println( output );
                if ( i < inputstring.length() )
                    combine( i + 1);
                output.setLength( output.length() - 1 );
            }
        }
        public static void main (String args[])
        {
            AllPossiblecombinations combobj= new AllPossiblecombinations("abc");
            System.out.println("All possible combinations are :  ");
            combobj.combine();
        }
         
}

Output

The input string  is  : abc
All possible combinations are : 
a
ab
abc
ac
b
bc
c

Algorithm Explanation

Get the string.
Append the letter to the output string and Print letters in output string
If the current letter isn’t the last in the input string Generate remaining combinations starting at next position with iteration starting at next letter beyond the letter just selected
Delete the last character of the output string.

Reference

  1. http://mathcentral.uregina.ca/QQ/database/QQ.09.06/candace1.html
  2. http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html

Write A Comment