Перестановки

class Solution
{
    public static void Bruteforce(List<int> nums, List<int> permutation, List<List<int>> allPermutations)
    {
        if (nums.Count == 0)
        {
            // Добавляем текущую комбинацию в список всех перестановок
            allPermutations.Add(new List<int>(permutation));
            return;
        }

        int n = nums.Count;
        for (int i = 0; i < n; i++)
        {
            int nextNum = nums[i];

            // Добавляем число в текущую перестановку и удаляем его из nums,
            // чтобы не использовать его повторно
            permutation.Add(nextNum);
            (nums[i], nums[nums.Count - 1]) = (nums[nums.Count - 1], nums[i]);
            nums.RemoveAt(nums.Count - 1);

            // Рекурсивный вызов для оставшихся чисел
            Bruteforce(nums, permutation, allPermutations);

            // Возвращаем состояние назад перед следующей итерацией
            nums.Add(nextNum);
            (nums[i], nums[nums.Count - 1]) = (nums[nums.Count - 1], nums[i]);
            permutation.RemoveAt(permutation.Count - 1);
        }
    }

    public static List<List<int>> Permutations(List<int> nums)
    {
        var allPermutations = new List<List<int>>();
        Bruteforce(nums, new List<int>(), allPermutations);
        return allPermutations;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

void bruteforce(vector<int>& nums, vector<int>& permutation, vector<vector<int>>& allPermutations) {
    if (nums.empty()) {
        // Добавляем текущую комбинацию в список всех перестановок
        allPermutations.push_back(permutation);
        return;
    }

    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int nextNum = nums[i];

        // Добавляем число в текущую перестановку и удаляем его из nums,
        // чтобы не использовать его повторно
        permutation.push_back(nextNum);
        swap(nums[i], nums[nums.size() - 1]);
        nums.pop_back();

        // Рекурсивный вызов для оставшихся чисел
        bruteforce(nums, permutation, allPermutations);

        // Возвращаем состояние назад перед следующей итерацией
        nums.push_back(nextNum);
        swap(nums[i], nums[nums.size() - 1]);
        permutation.pop_back();
    }
}

vector<vector<int>> permutations(vector<int> nums) {
    vector<vector<int>> allPermutations;
    vector<int> permutation;
    bruteforce(nums, permutation, allPermutations);
    return allPermutations;
}

package main

func bruteforce(nums []int, permutation []int, allPermutations *[][]int) {
    if len(nums) == 0 {
        // Добавляем текущую комбинацию в список всех перестановок
        permutationCopy := append([]int{}, permutation...)
        *allPermutations = append(*allPermutations, permutationCopy)
        return
    }

    n := len(nums)
    for i := 0; i < n; i++ {
        nextNum := nums[i]

        // Добавляем число в текущую перестановку и удаляем его из nums,
        // чтобы не использовать его повторно
        permutation = append(permutation, nextNum)
        nums[i], nums[n-1] = nums[n-1], nums[i]
        nums = nums[:n-1]

        // Рекурсивный вызов для оставшихся чисел
        bruteforce(nums, permutation, allPermutations)

        // Возвращаем состояние назад перед следующей итерацией
        nums = append(nums, nextNum)
        nums[i], nums[n-1] = nums[n-1], nums[i]
        permutation = permutation[:len(permutation)-1]
    }
}

func permutations(nums []int) [][]int {
    allPermutations := [][]int{}
    permutation := []int{}
    bruteforce(nums, permutation, &allPermutations)
    return allPermutations
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    private static void swap(List<Integer> list, int i, int j) {
        int tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }

    public static void bruteforce(List<Integer> nums, List<Integer> permutation, List<List<Integer>> allPermutations) {
        if (nums.isEmpty()) {
            // Добавляем текущую комбинацию в список всех перестановок
            allPermutations.add(new ArrayList<>(permutation));
            return;
        }

        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int nextNum = nums.get(i);

            // Добавляем число в текущую перестановку и удаляем его из nums,
            // чтобы не использовать его повторно
            permutation.add(nextNum);
            swap(nums, i, n - 1);
            nums.remove(n - 1);

            // Рекурсивный вызов для оставшихся чисел
            bruteforce(nums, permutation, allPermutations);

            // Возвращаем состояние назад перед следующей итерацией
            nums.add(nextNum);
            swap(nums, i, n - 1);
            permutation.remove(permutation.size() - 1);
        }
    }

    public static List<List<Integer>> permutations(List<Integer> nums) {
        List<List<Integer>> allPermutations = new ArrayList<>();
        bruteforce(nums, new ArrayList<>(), allPermutations);
        return allPermutations;
    }
}

from typing import *

def bruteforce(nums: List[int], permutation: List[int], all_permutations: List[List[int]]):
    if len(nums) == 0:
        # Добавляем текущую комбинацию в список всех перестановок
        all_permutations.append(permutation[:])
        return

    # Перебираем все возможные варианты
    n = len(nums)
    for i in range(n):
        next_num = nums[i]

        # Добавляем число в текущую перестановку и удаляем его из nums
        # чтобы не использовать его повторно
        permutation.append(next_num)
        nums[i], nums[-1] = nums[-1], nums[i]
        nums.pop()

        bruteforce(nums, permutation, all_permutations)

        # Возвращаем состояние назад перед следующей итерацией
        nums.append(next_num)
        nums[i], nums[-1] = nums[-1], nums[i]
        permutation.pop()

def permutations(nums: List[int]) -> List[List[int]]:
    all_permutations = []
    bruteforce(nums, [], all_permutations)
    return all_permutations

export function bruteforce(nums, permutation, allPermutations) {
    if (nums.length === 0) {
        // Добавляем текущую комбинацию в список всех перестановок
        allPermutations.push(permutation.slice());
        return;
    }

    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const nextNum = nums[i];

        // Добавляем число в текущую перестановку и удаляем его из nums,
        // чтобы не использовать его повторно
        permutation.push(nextNum);
        [nums[i], nums[n - 1]] = [nums[n - 1], nums[i]];
        const removed = nums.pop();

        // Рекурсивный вызов для оставшихся чисел
        bruteforce(nums, permutation, allPermutations);

        // Возвращаем состояние назад перед следующей итерацией
        nums.push(removed);
        [nums[i], nums[n - 1]] = [nums[n - 1], nums[i]];
        permutation.pop();
    }
}

export function permutations(nums) {
    const allPermutations = [];
    bruteforce(nums, [], allPermutations);
    return allPermutations;
}