LeetCode - 순열

문제 설명

개별 정수의 배열 숫자가 주어지면 가능한 모든 순열을 반환합니다. 어떤 순서로든 답변을 반환할 수 있습니다.

문제 진술 출처: 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]);
            }
        }
    }
};

골랑 솔루션

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]
        }
    }
}

자바스크립트 솔루션

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]]