【Leecode】Leecode刷题之路第46天之全排列

题目出处

46-全排列-题目出处

题目描述

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

46-全排列-官方解法

• 预备知识
  
  回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

方法1：回溯

思路：

代码示例：（Java）

public class Solution1 {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> output = new ArrayList<Integer>();for (int num : nums) {output.add(num);}int n = nums.length;backtrack(n, output, res, 0);return res;}public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {// 所有数都填完了if (first == n) {res.add(new ArrayList<Integer>(output));}for (int i = first; i < n; i++) {// 动态维护数组Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first + 1);// 撤销操作Collections.swap(output, first, i);}}}

复杂度分析

考察知识点

1.排列

收获

Gitee源码位置

46-全排列-源码