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


Постановка задачи

Задав массив nums из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.

Постановка задачи взята с сайта: https://leetcode.com/problems/permutations

Пример 1:

Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Вход в полноэкранный режим Выход из полноэкранного режима

Пример 2:

Input: nums = [0, 1]
Output: [[0, 1], [1, 0]]
Вход в полноэкранный режим Выход из полноэкранного режима

Пример 3:

Input: nums = [1]
Output: [[1]]
Войти в полноэкранный режим Выход из полноэкранного режима

Ограничения:

- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
Войти в полноэкранный режим Выйти из полноэкранного режима

Объяснение

Рекурсия

Когда нам нужно сгенерировать перестановку или последовательность, лучше всего использовать рекурсию. Рекурсия для этой задачи будет немного отличаться от стандартной рекурсии.

Один из подходов к решению этой проблемы заключается в том, чтобы отслеживать элемент, который мы посетили, и генерировать перестановки для остальных элементов массива. Но мы можем решить эту проблему, поменяв местами элементы массива.

Давайте перейдем к алгоритму, чтобы лучше понять его.

- set result = [[]]

- call _getPermutations(result, nums, 0, nums.length - 1)

- return result

// _getPermutations(result, nums, l, r)
- if l == r
  - push the current nums permutation in the result
  - result.push(nums)
- else
  - loop for i = l; i <= r; i++
    - swap(nums[l], nums[i])

    - _getPermutations(result, nums, l + 1, r)

    - swap(nums[l], nums[i])
- end if
Вход в полноэкранный режим Выход из полноэкранного режима

Давайте проверим наш алгоритм на C++, Golang и Javascript.

Решение на C++

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;

        _getPermutations(result, nums, 0, nums.size() - 1);
        return result;
    }

    void _getPermutations(vector<vector<int>>& result, vector<int> nums, int l, int r){
        if(l == r){
            result.push_back(nums);
            return;
        } else {
            for(int i = l; i <= r; i++){
                swap(nums[l], nums[i]);

                _getPermutations(result, nums, l + 1, r);

                swap(nums[l], nums[i]);
            }
        }
    }
};
Вход в полноэкранный режим Выход из полноэкранного режима

Решение на Golang

func permute(nums []int) [][]int {
    result := [][]int{}

    _getPermutations(&result, nums, 0, len(nums) - 1)

    return result
}

func _getPermutations(result *[][]int, nums []int, l, r int) {
    if l == r {
        cp := make([]int, len(nums))
        copy(cp, nums)
        *result = append(*result, cp)
    } else {
        for i := l; i <= r; i++ {
            nums[l], nums[i] = nums[i], nums[l]

            _getPermutations(result, nums, l + 1, r)

            nums[l], nums[i] = nums[i], nums[l]
        }
    }
}
Войти в полноэкранный режим Выход из полноэкранного режима

Решение для Javascript

var permute = function(nums) {
    const result = [];

    _getPermutations(result, nums, 0, nums.length - 1);

    return result;
};

function _getPermutations(result, nums, l, r) {
    if(l === r) {
        result.push(nums.slice(0));
        return;
    } else {
        for(let i = l; i <= r; i++) {
            [nums[l], nums[i]] = [nums[i], nums[l]];

            _getPermutations(result, nums, l + 1, r);

            [nums[l], nums[i]] = [nums[i], nums[l]];
        }
    }
}
Войти в полноэкранный режим Выход из полноэкранного режима

Давайте проверим наш алгоритм для примера 1.

Input: nums = [1, 2, 3]

// in permute function
Step 1: vector<vector<int>> result

Step 2: _getPermutations(result, nums, 0, nums.size() - 1)
        _getPermutations(result, nums, 0, 2)

// in _getPermutations function
Step 3: if l == r
           0 == 2
           false

        else
          loop for i = l; i <= r
            i = 0
            0 <= 2
            true

            swap(nums[l], nums[i])
            swap(nums[0], nums[0])
            nums = [1, 2, 3]

            _getPermutations(result, nums, l + 1, r)
            _getPermutations(result, nums, 0 + 1, 2)
            _getPermutations(result, nums, 1, 2)

Step 4: if l == r
           1 == 2
           false

        else
          loop for i = l; i <= r
            i = 1
            1 <= 2
            true

            swap(nums[l], nums[i])
            swap(nums[1], nums[1])
            nums = [1, 2, 3]

            _getPermutations(result, nums, l + 1, r)
            _getPermutations(result, nums, 1 + 1, 2)
            _getPermutations(result, nums, 2, 2)

Step 5: if l == r
           2 == 2
           true
           result.push_back(nums)
           result = [[1, 2, 3]]
           return

           // We return to step 4

Step 6: swap(nums[l], nums[i])
        swap(nums[1], nums[1])
        nums = [1, 2, 3]

        i++
        i = 2
        loop for i <= r
            i = 2
            2 <= 2
            true

            swap(nums[l], nums[i])
            swap(nums[1], nums[2])
            nums = [1, 3, 2]

            _getPermutations(result, nums, l + 1, r)
            _getPermutations(result, nums, 1 + 1, 2)
            _getPermutations(result, nums, 2, 2)

Step 7: if l == r
           2 == 2
           true
           result.push_back(nums)
           result = [[1, 2, 3], [1, 3, 2]]
           return

           // We return to step 6

Step 8: swap(nums[l], nums[i])
        swap(nums[1], nums[2])
        nums = [1, 2, 3]

        i++
        i = 3
        loop for i <= r
            i = 3
            3 <= 2
            false

        // we backtrack to step 3

Step 9: swap(nums[l], nums[i])
        swap(nums[0], nums[0])
        nums = [1, 2, 3]

        i++
        i = 1
        loop for i <= r
            i = 1
            1 <= 2
            true

            swap(nums[l], nums[i])
            swap(nums[0], nums[1])
            nums = [2, 1, 3]

            _getPermutations(result, nums, l + 1, r)
            _getPermutations(result, nums, 0 + 1, 2)
            _getPermutations(result, nums, 1, 2)

Step 10: if l == r
            1 == 2
            false

         else
            for i = l; i <= r
            i = 1
            1 <= 2
            true

            swap(nums[l], nums[i])
            swap(nums[1], nums[1])
            nums = [2, 1, 3]

            _getPermutations(result, nums, l + 1, r)
            _getPermutations(result, nums, 1 + 1, 2)
            _getPermutations(result, nums, 2, 2)

Step 11: if l == r
            2 == 2
            true
            result.push_back(nums)
            result = [[1, 2, 3], [1, 3, 2], [2, 1, 3]]
            return

            // We return to step 10

We similarly backtrack to generate the rest of the solution
We return the solution as

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий