Постановка задачи
Учитывая массив 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.
С++ решение
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] } } }
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>> resultStep 2: _getPermutations(result, nums, 0, nums.size() - 1) _getPermutations(result, nums, 0, 2)// in _getPermutations function Step 3: if l == r 0 == 2 falseelse loop for i = l; i <= r i = 0 0 <= 2 trueswap(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 falseelse loop for i = l; i <= r i = 1 1 <= 2 trueswap(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 trueswap(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 trueswap(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 falseelse for i = l; i <= r i = 1 1 <= 2 trueswap(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]]
Первоначально опубликовано на https://alkeshghorpade.me.
