Question
Formatted question description: https://leetcode.ca/all/46.html
46. Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
@tag-backtracking
Algorithm
When n=1, there is only one number a1 in the array, and there is only one total permutation, which is a1
When n=2
, there is a1a2
in the array at this time, and there are two kinds of full arrays, a1a2
and a2a1
. Then, considering the relationship with the above situation at this time, you can find that it is actually added in the two positions before and after a1. A2
When n=3
, there are a1a2a3
in the array. At this time, there are six kinds of full arrays, namely a1a2a3
, a1a3a2
, a2a1a3
, a2a3a1
, a3a1a2
, and a3a2a1
. Then according to the above conclusion, it is actually obtained by adding a3
at different positions on the basis of a1a2 and a2a1.
_ a1 _ a2 _
: a3a1a2, a1a3a2, a1a2a3
_ a2 _ a1 _
: a3a2a1, a2a3a1, a2a1a3
Code
Java
-
import java.util.ArrayList; import java.util.HashSet; import java.util.List; public class Permutations { public static void main(String[] args) { Permutations out = new Permutations(); Solution_iteration s = out.new Solution_iteration(); System.out.println(s.permute(new int[]{1, 2, 3})); } // time: O(N) // space: O(N) public class Solution_iteration { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); if (nums == null || nums.length == 0) { return list; } list.add(new ArrayList<Integer>()); // add empty single list, to make below loop going for (int i = 0; i < nums.length; i++) { List<List<Integer>> tmpList = new ArrayList<>(); int insertNum = nums[i]; // get each permutations. eg, [1,2], [2,1] for (List<Integer> singlePerm: list) { // eg. [1,2] and insert 3, there are 3 insert position int singleListSize = singlePerm.size(); for (int index = 0; index <= singleListSize; index++) { // @note: the usage of arraylist add() api: add(atIndex, value) singlePerm.add(index, insertNum); tmpList.add(new ArrayList<Integer>(singlePerm)); // @note: don't forget roll back singlePerm.remove(index); } } // update list. @note: possible issue, this is not deep copy list = tmpList; } return list; } } // time: O(N) // space: O(N) class Solution_dfs { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { if (nums == null || nums.length == 0) { return result; } dfs(nums, new HashSet<Integer>(), new ArrayList<Integer>()); // hashset 或者是boolean[] return result; } private void dfs(int[] nums, HashSet<Integer> isVisited, ArrayList<Integer> onePath) { if (isVisited.size() == nums.length) { result.add(new ArrayList<>(onePath)); return; } for (int i = 0; i < nums.length; i++) { if (!isVisited.contains(i)) { isVisited.add(i); onePath.add(nums[i]); dfs(nums, isVisited, onePath); isVisited.remove(i); onePath.remove(onePath.size() - 1); } } } } }
-
// OJ: https://leetcode.com/problems/permutations/ // Time: O(N!) // Space: O(N) class Solution { vector<vector<int>> ans; void dfs(vector<int> &nums, int start) { if (start == nums.size() - 1) { ans.push_back(nums); return; } for (int i = start; i < nums.size(); ++i) { swap(nums[i], nums[start]); dfs(nums, start + 1); swap(nums[i], nums[start]); } } public: vector<vector<int>> permute(vector<int>& nums) { dfs(nums, 0); return ans; } };
-
class Solution(object): def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [] visited = set([]) def dfs(nums, path, res, visited): if len(path) == len(nums): res.append(path + []) return for i in range(0, len(nums)): # if i > 0 and nums[i - 1] == nums[i]: # continue if i not in visited: visited.add(i) path.append(nums[i]) dfs(nums, path, res, visited) path.pop() visited.discard(i) dfs(nums, [], res, visited) return res