[LeetCode] 46. Permutations

全排列。给一个没有重复元素的数组,请返回这个数组所有可能的全排列。

例子,

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 }

 

上一篇:图漾科技产品列表2020-02


下一篇:yb课堂 核心数据库表字段设计和测试数据准备 《一》