Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 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]]
Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1] Output: [[1]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Solution 1: DFS (Backtracking)
We design a function
The time complexity is
Similar problems:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(permutations(nums))class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
if i == n:
ans.append(t[:])
return
for j in range(n):
if not vis[j]:
vis[j] = True
t[i] = nums[j]
dfs(i + 1)
vis[j] = False
n = len(nums)
vis = [False] * n
t = [0] * n
ans = []
dfs(0)
return ansclass Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
nonlocal mask
if i == n:
ans.append(t[:])
return
for j in range(n):
if (mask >> j & 1) == 0:
mask |= 1 << j
t[i] = nums[j]
dfs(i + 1)
mask ^= 1 << j
n = len(nums)
mask = 0
t = [0] * n
ans = []
dfs(0)
return ansclass Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private boolean[] vis;
private int[] nums;
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
vis = new boolean[nums.length];
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
for (int j = 0; j < nums.length; ++j) {
if (!vis[j]) {
vis[j] = true;
t.add(nums[j]);
dfs(i + 1);
t.remove(t.size() - 1);
vis[j] = false;
}
}
}
}class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
vector<int> t(n);
vector<bool> vis(n);
function<void(int)> dfs = [&](int i) {
if (i == n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t[i] = nums[j];
dfs(i + 1);
vis[j] = false;
}
}
};
dfs(0);
return ans;
}
};func permute(nums []int) (ans [][]int) {
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(t))
return
}
for j, v := range nums {
if !vis[j] {
vis[j] = true
t[i] = v
dfs(i + 1)
vis[j] = false
}
}
}
dfs(0)
return
}/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
const ans = [];
const t = [];
const vis = new Array(n).fill(false);
function dfs(i) {
if (i >= n) {
ans.push([...t]);
return;
}
for (let j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t.push(nums[j]);
dfs(i + 1);
vis[j] = false;
t.pop();
}
}
}
dfs(0);
return ans;
};public class Solution {
public IList<IList<int>> Permute(int[] nums) {
var ans = new List<IList<int>>();
var t = new List<int>();
var vis = new bool[nums.Length];
dfs(nums, 0, t, vis, ans);
return ans;
}
private void dfs(int[] nums, int i, IList<int> t, bool[] vis, IList<IList<int>> ans) {
if (i >= nums.Length) {
ans.Add(new List<int>(t));
return;
}
for (int j = 0; j < nums.Length; ++j) {
if (!vis[j]) {
vis[j] = true;
t.Add(nums[j]);
dfs(nums, i + 1, t, vis, ans);
t.RemoveAt(t.Count - 1);
vis[j] = false;
}
}
}
}function permute(nums: number[]): number[][] {
const n = nums.length;
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...nums]);
}
for (let j = i; j < n; j++) {
[nums[i], nums[j]] = [nums[j], nums[i]];
dfs(i + 1);
[nums[i], nums[j]] = [nums[j], nums[i]];
}
};
dfs(0);
return res;
}impl Solution {
fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
let n = nums.len();
if i == n {
res.push(nums.clone());
return;
}
for j in i..n {
nums.swap(i, j);
Self::dfs(i + 1, nums, res);
nums.swap(i, j);
}
}
pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(0, &mut nums, &mut res);
res
}
}impl Solution {
#[allow(dead_code)]
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ret = Vec::new();
let mut cur_vec = Vec::new();
let mut vis = vec![false; nums.len() + 1];
Self::dfs(&nums, &mut vis, 0, &mut cur_vec, &mut ret);
ret
}
#[allow(dead_code)]
fn dfs(
nums: &Vec<i32>,
vis: &mut Vec<bool>,
index: i32,
cur_vec: &mut Vec<i32>,
ans: &mut Vec<Vec<i32>>
) {
let n = nums.len();
if (index as usize) == n {
ans.push(cur_vec.clone());
return;
}
// Otherwise, let's iterate the nums vector
for i in 0..n {
if !vis[i] {
// If this number hasn't been visited, then visit it
vis[i] = true;
cur_vec.push(nums[i]);
Self::dfs(nums, vis, index + 1, cur_vec, ans);
// Reset the changes
cur_vec.pop().unwrap();
vis[i] = false;
}
}
}
}