CareerCup

private static String input;

private static void generateCombinations(String string) {
input = string;
_generateCombinations("", 0, true);
}

private static void _generateCombinations(String currentString,
int currentIndex, boolean print){
if(currentIndex >= input.length()){
if(print)
System.out.println(currentString);
return;
}
if(print)
System.out.println(currentString);
_generateCombinations(currentString + input.charAt(currentIndex), currentIndex + 1, true);
_generateCombinations(currentString, currentIndex + 1, false);
}

It is nothing but to write all the subsets of a given set except the empty set.

1. Find the number 2^n -1.
2. Starting from one, write all the numbers till 2^n -1 in binary form.
3. The places where '1' occur, replace them with the corresponding index in array.

Ex: {a,b,c}

Soln: n=3
N = 2^3-1 = 7

001 - c
010 - b
011 - b,c
100 - a
101 - a,c
110 - a,b
111 - a,b,c

Clear, comprehensible and crisp. :)

one possible approach using backtracking.
Total no of string would be 2^N-1.

#include <stdio.h>
#include <string.h>
void combination(char *string, char *temp, int start, int depth, int length)
{
int i;
if( start <= length && start != 0)
{
temp[depth+1] = '\0';
printf("%s\n ", temp);
}
for(i=start; i<length; i++)
{
temp[depth] = string[i];
combination(string, temp, i+1, depth, length);
temp[depth] = string[i];
depth++;
}
}

int main()
{
char string[]="abcd";
char temp[strlen(string)+1];
combination(string, temp, 0, 0, strlen(string));
return 0;
}

public void getCombinations(String str) {
System.out.println(str.length());
for ( int i =0 ; i < str.length();i++) {
for ( int j=i+1;j<=str.length();j++) {
System.out.println(str.substring(i,j));
}
}


}
This is working for me..any thoughts?

An approach without backtracking with O(1) space.

#include <stdio.h>
#include <string.h>
#include <math.h>
 
void comb(char *str)
{
        int n,i,j,top,wt;
        n=strlen(str);
        n=pow(2,n);
 
        for(i=1;i<n;i++)
        {
                for(j=i,wt=1,top=0;j>0;j>>=1,top++)
                {
                        if(j&wt)
                                printf("%c",str[top]);
                }
                printf("\n");
        }
}
 
int main()
{
        char str[]="ABCD";
        comb(str);
        return 0;
}

ideone.com/A5Ucq

public ArrayList getCombinations(String str) {
ArrayList<String> a = new ArrayList<String>();
// System.out.println(a.size());
// a.add("xx");
for ( int i =0 ; i < str.length();i++) {

int k=a.size();
for ( int j=0;j<k;j++)
{
System.out.println(a.get(j)+str.charAt(i));
a.add(a.get(j)+str.charAt(i));
}
a.add(str.charAt(i)+"");
// System.out.println(a.get(0));
}

return a;
}

This should work

Take number 0 and increment it upto 2^n-1.
When its zero,get all its set bits and use them as index into the array for printing hence ""
for 1, output d
for 2,output c
for 3, output cd
for 4, output b
and so on....