מריה בוטוסוב

נותנים מערך של מספרים, יש למצוא את כל הפרמוטציות שלו.

//N*N! Time
//N*N! Space
public static List<List<int>> GetALLPermutations(List<int> array) {
    List<List<int>> result = new List<List<int>>();		
    BuildPermutations(0, array, result);
    return result;
}
    
private static void BuildPermutations(int i, List<int> array, List<List<int>> permutations) {
    if (i == array.Count - 1) 
        permutations.Add(new List<int>(array)); //N
    else {
        for (int j = i; j < array.Count;j++) {
            swap(array, i, j);
            BuildPermutations(i+1, array, permutations); //N!
            swap(array, i, j);
        } 
    }
}
    
public static void swap(List<int> array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}