问题陈述

给定一个由不同整数组成的数组，返回所有可能的排列。 您可以按任何顺序返回答案。

示例 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> permute(vector& nums) {
        vector> result;        _getPermutations(result, nums, 0, nums.size() - 1);
        return result;
    }    void _getPermutations(vector>& result, vector 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> resultStep 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 4Step 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 6Step 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 3Step 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 10We 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]]

关注七爪网，获取更多APP/小程序/网站源码资源！