All Permutations of String

解题思路1：回溯+DFS

和Permutation II是完全一样的。

void permute( String input) {
    int inputLength = input.length();
    boolean[ ] used = new boolean[ inputLength ];

    StringBuffer outputString = new StringBuffer();
    char[] in = input.toCharArray( );
    Arrays.sort(in);

    doPermute(in, outputString, used);
}

void doPermute ( char[ ] in, StringBuffer current,
                     boolean[ ] used) {

    if( current.length() == in.length) {
        System.out.println(current.toString());
        return;
    }

    for( int i = 0; i < in.length; ++i ) {
        if( used[i] )
              continue;

        if (i > 0 && in[i] == in[i-1] && used[i-1] == false){
            continue;
        }

        current.append( in[i] );
        used[i] = true;
        doPermute( in,   current, used);
        used[i] = false;
        current.deleteCharAt(current.length() - 1);
        //current.setLength(   current.length() - 1 );
    }
}

References

1 Programming Interview Questions 11: All Permutations of String

2 permutations-of-a-string

3 Permutations.java