Leetcode 46 - Permutations

Note:

  • This is a backtracking problem.
  • We don’t need startIndex because each path must contain all elements.
  • We do need a used array to keep track if we’ve used the element.

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example

1
2
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let result = [];
let path = [];
let used = new Set();
backtracking(used);
return result;

function backtracking(used) {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used.has(i)) continue;
path.push(nums[i]);
used.add(i);
backtracking(used);
path.pop();
used.delete(i);
}
}
};