Before you begin


  • 0
    J

    Before you begin thinking about the implementation details, I thought it was helpful to write out the algorithm by hand. To avoid confusion with indexes, this problem is easier to think of in terms of letters as opposed to numbers. For example, given "ABCD", the gist of the algorithm is to start with permutations of A, then permutations of AB, then permutations of ABC, etc. The logic goes like this:

    Input:     A B C D
    Input Idx: 0 1 2 3
    [A]        // insert input[0] to pos 0 of 1st row []
    [B A       // insert input[1] to pos 0 of 1st row [A]
     A B]      // insert input[1] to pos 1 of 1st row [A]
    [C B A     // insert input[2] to pos 0 of 1st row [BA]
     C A B     // insert input[2] to pos 0 of 2nd row [AB]
     B C A     // insert input[2] to pos 1 of 1st row [BA]
     A C B     // insert input[2] to pos 1 of 2nd row [AB]
     B A C     // insert input[2] to pos 2 of 1st row [BA]
     A B C]    // insert input[2] to pos 2 of 2nd row [AB]
    [D C B A   // insert input[3] to pos 0 of 1st row [CBA]
     D C A B   // insert input[3] to pos 0 of 2nd row [CAB]
     D B C A   // insert input[3] to pos 0 of 3rd row [BCA]
     …
     A B C D]   // insert input[3] to pos 3 of 6th row [ABC]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.