Permutations
Problem
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]]
Pseudocode
- dfs with a for loop within
- permutation with backtracking
- same as combination sum, don't understand this intuitively
Solution
// from solutions
// https://leetcode.com/problems/permutations/solutions/685868/dfs-backtracking-python-java-javascript-picture/
// good illustration on how to approach the problem
// time O(N^N), has to find every permutation
var permute = function (nums) {
let res = [];
dfs(nums, [], Array(nums.length).fill(false), res);
return res;
};
function dfs(nums, path, used, res) {
// console.log(path)
if (path.length == nums.length) {
// make a deep copy since otherwise we'd be append the same list over and over
res.push(Array.from(path));
return;
}
for (let i = 0; i < nums.length; i++) {
// skip used nums
if (used[i]) continue;
// add letter to permutation, mark letter as used
path.push(nums[i]);
used[i] = true;
dfs(nums, path, used, res);
// remove letter from permutation, mark letter as unused
path.pop();
used[i] = false;
}
}
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated