全排列。给一个没有重复元素的数组,请返回这个数组所有可能的全排列。
例子,
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
这是backtracking(回溯)类题目的经典题。遇到回溯类型的题,基本思路参见这个帖子,讲的很好。回溯的题一般都需要有一个helper函数帮助做DFS的操作。helper函数的返回条件是子数组的长度跟数组长度一致。之后就是遍历input数组,如果没有遍历到某个数字,就加入结果集,然后再回溯。
时间O(n! * n)
空间O(n)
1 /** 2 * @param {number[]} nums 3 * @return {number[][]} 4 */ 5 var permute = function (nums) { 6 let res = []; 7 if (nums === null || nums.length === 0) return res; 8 helper(res, [], nums); 9 return res; 10 }; 11 12 var helper = function (res, list, nums) { 13 if (list.length === nums.length) { 14 res.push(list.slice()); 15 return; 16 } 17 for (let i = 0; i < nums.length; i++) { 18 if (list.includes(nums[i])) { 19 continue; 20 } 21 list.push(nums[i]); 22 helper(res, list, nums); 23 list.pop(); 24 } 25 }